【DP】118.杨辉三角

题目

Python

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = list()
        for i in range(numRows):
            tmp_list = list()
            for j in range(0, i+1):
                if j == 0 or j == i:
                    tmp_list.append(1)
                else:
                    tmp_list.append(res[i-1][j-1] + res[i-1][j])
            res.append(tmp_list)

        return res

Java

法1：dp

简单dp!

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>(Arrays.asList(1));
        res.add(new ArrayList<>(tmp));
        for (int i = 1; i < numRows; ++i) {
            List<Integer> preList = res.get(i - 1);
            tmp.clear();
            tmp.add(1);
            for (int k = 1; k < i; ++k) {
                tmp.add(preList.get(k - 1) + preList.get(k));
            }
            tmp.add(1);
            res.add(new ArrayList<>(tmp));
        }

        return res;
    }
}