leetcode——[118]Pascal's Triangle杨辉三角

题目

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

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

示例:

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

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解题方法

动态规划

每一行都可以根据上一行来计算，第一行为[1]。行数为0时，返回一个空列表；结果添加首行，然后循环添加后续行，每次循环根据上一行来计算当前行，需要利用杨辉三角的特征：首尾项为1，第i项为上一行第i-1项和第i项的和。这段代码跑了1ms，超过了95.26%的Java提交。

public class Solution {
    // Method 1 1ms 95.26%
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows == 0) {
            return res;
        }
        res.add(Arrays.asList(1));
        for (int i = 1; i < numRows ; i++) {
            List<Integer> subList = new ArrayList<>();
            List<Integer> preList = res.get(i - 1);
            subList.add(1);
            for (int j = 1; j < i; j++) {
                subList.add(preList.get(j - 1) + preList.get(j));
            }
            subList.add(1);
            res.add(subList);
        }
        return res;
    }
}