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

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

示例 1:

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

示例 2:

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

解题思路

• 定义状态： dp[i-1][j-1] 就是第 i 行第 j 个数字的值

• 基础情况： 第 i 行首个元素和末个元素值为 1

  • dp[i][0] = 1
  • dp[i][i] = 1

• 转移方程：某个数字的值 = 其上方数字的值 + 上方左侧数字的值

  • dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

动态初始化数组，如下声明一个 numRows 行的数组，列数暂不声明

Integer[][] dp = new Integer[numRows][];

[
 [], 
 [], 
 [], 
 [], 
 []
    ]

然后for循环动态初始化列

for (int i = 0; i < numRows ; i++){
    // 动态生成列
    dp[i] = new Integer[i+1];
}

Java 实现

    public List<List<Integer>> generate(int numRows) {
        // 先声明 numRows 行，列数暂不声明
        Integer[][] dp = new Integer[numRows][];
        for (int i = 0; i < numRows ; i++){
            // 动态生成列
            dp[i] = new Integer[i+1];
            // 第 i 行首个元素和末个元素值为1
            dp[i][0] = 1;
            dp[i][i] = 1;
            // 其他元素
            for (int j = 1; j < i; j++){
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            }
        }
        List<List<Integer>> resultList = new ArrayList<>();
        for (Integer[] row : dp){
            resultList.add(Arrays.asList(row));
        }
        return resultList;
    }