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，第一个和最后一个值为1.状态转移方程为当前数等于上一行的相邻两个元素之和。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        Integer[][] dp = new Integer[numRows][];
        for(int i = 0;i < numRows;i++){
            dp[i] = new Integer[i + 1];
            dp[i][0] = dp[i][i] = 1;
            for(int j = 1;j < i;j++){
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        for(Integer[] num : dp){
            ans.add(Arrays.asList(num));
        }
        return ans;
    }
}