Problem: 118. 杨辉三角

题目描述

思路

1.初始化状态：将创建的二维数组dp的第一列和主对角线上元素设为1；
2.状态的转移：从第一行、列起始，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

class Solution {
    /**
     * Generates Yanghui triangle
     *
     * @param numRows The number of rows
     * @return List<List < Integer>>
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> dp = new ArrayList<>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> subList = new ArrayList<>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    subList.add(1);
                } else {
                    subList.add(dp.get(i - 1).get(j - 1) + dp.get(i - 1).get(j));
                }
            }
            dp.add(subList);
        }
        return dp;
    }
}