118 杨辉三角

[hitolz]

简单动态规划 a[i][j] = a[i-1][j-1]+a[i-1][j]

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();

        if (numRows == 0) {
            return result;
        }

        int[][] num = new int[100][100];
        num[0][0] = 1;
        tmp.add(num[0][0]);
        if (numRows >= 1) {
            result.add(tmp);
        }

        tmp = new ArrayList<>();
        num[1][0] = 1;
        num[1][1] = 1;

        tmp.add(num[1][0]);
        tmp.add(num[1][1]);
        if (numRows >= 2) {
            result.add(tmp);
        }

        if (numRows > 2) {
            for (int i = 2; i < numRows; i++) {
                tmp = new ArrayList<>();
                num[i][0] = 1;
                num[i][i] = 1;
                tmp.add(num[i][0]);
                for (int j = 1; j < i; j++) {
                    num[i][j] = num[i - 1][j - 1] + num[i - 1][j];
                    tmp.add(num[i][j]);
                }
                tmp.add(num[i][i]);
                result.add(tmp);

            }
        }
        return result;
    }
}