杨辉三角

原题链接

使用的方法

• 动态规划

解题思路

杨辉三角的每一行都是由上一行生成的。具体来说，第n行的第i个元素等于上一行的第i-1个元素与第i个元素之和。因此，我们可以使用动态规划来解决这个问题。
dp公式：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

代码实现

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList();
        // 循环到n行
        for(int i=0;i< numRows;i++){
            List<Integer> row = new ArrayList<>(i+1);
            // 先此行将所有填入1
            for(int k=0;k<=i;k++){
                row.add(1);
            }
            // 因为两边都是1，循环从1开始，到i-1结束
            for(int j=1;j<=i-1;j++){
                row.set(j,res.get(i-1).get(j-1) + res.get(i-1).get(j));
            }
            res.add(row);
        }
        return res;
    }
}