# 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) {
} else {
}
}
}
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

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) {
} else {
}
}
}
return res;
}
}
``````

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

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.

// 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++) {
}

// The last row element is always 1.

}

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;
for (int j = 1; j <= i; j++) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}