LeetCode刷题【118】杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

• 1 <= numRows <= 30

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> rowList = new ArrayList<>();
        rowList.add(1);
        res.add(rowList);
        for (int row = 1; row < numRows; row++) {
            List<Integer> tmpRowList = new ArrayList<>();
            for (int col = 0; col <= row; col++) {
                int leftUp = col== 0 ? 0 :res.get(row-1).get(col-1);
                int rightUp = col == row? 0 :res.get(row-1).get(col);
                tmpRowList.add(leftUp+rightUp);
            }
            res.add(tmpRowList);
        }
        return res;
    }
}

把原来的题目中的图全部往左靠了偏移，然后我们再在左右两边都加上不存在的虚拟出来的0

方法直接呼之欲出

dp[i][n] = dp[i-1][n] + dp[i-1][n-1]

更多相关可以参考LeetCode刷题【119】杨辉三角 II