Pascal's Triangle

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]
]

Analysis

DP的初始条件也就是第一行[1], 第二行[1, 1]
每一层之间的递推关系很直观:
row[i] = lastRow[i] + lastRow[j - 1]
因此只需要按此写出代码即可。

Solution

Dynamic Programming O(n^2) time (0ms 100% AC)
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<Integer>();
List<Integer> lastRow = i > 0 ? res.get(i - 1) : new ArrayList<Integer>();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
row.add(1);
} else {
row.add(lastRow.get(j) + lastRow.get(j - 1));
}
}
res.add(row);
}
return res;
}
}
Another Implementation
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
// 1st base case
if (numRows == 0) return res;
// 2nd base case
res.add(new ArrayList<>());
res.get(0).add(1);
for (int i = 1; i < numRows; i++) {
List<Integer> row = new ArrayList<Integer>();
List<Integer> lastRow = res.get(i - 1);
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
row.add(1);
} else {
row.add(lastRow.get(j) + lastRow.get(j - 1));
}
}
res.add(row);
}
return res;
}
}
DP (LeetCode official answer)
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<List<Integer>>();
// First base case; if user requests zero rows, they get zero rows.
if (numRows == 0) {
return triangle;
}
// Second base case; first row is always [1].
triangle.add(new ArrayList<>());
triangle.get(0).add(1);
for (int rowNum = 1; rowNum < numRows; rowNum++) {
List<Integer> row = new ArrayList<>();
List<Integer> prevRow = triangle.get(rowNum-1);
// The first row element is always 1.
row.add(1);
// Each triangle element (other than the first and last of each row)
// is equal to the sum of the elements above-and-to-the-left and
// above-and-to-the-right.
for (int j = 1; j < rowNum; j++) {
row.add(prevRow.get(j-1) + prevRow.get(j));
}
// The last row element is always 1.
row.add(1);
triangle.add(row);
}
return triangle;
}
}
DP - 2D array - O(n^2) time, O(n^2) space
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<>();
if (numRows == 0) {
return result;
}
int[][] dp = new int[numRows][numRows];
List<Integer> row;
for (int i = 0; i < numRows; i++) {
row = new ArrayList<Integer>();
dp[i][0] = 1;
row.add(dp[i][0]);
for (int j = 1; j <= i; j++) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
row.add(dp[i][j]);
}
result.add(row);
}
return result;
}
}

Reference