# Pascal's Triangle

Given a non-negative integer *numRows*, generate the first \_numRows \_of Pascal's triangle.

![](https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif)\
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]`

每一层之间的递推关系很直观：

```java
row[i] = lastRow[i] + lastRow[j - 1]
```

因此只需要按此写出代码即可。

## Solution

**Dynamic Programming O(n^2) time (0ms 100% AC)**

```java
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

```java
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)**

```java
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

```java
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

<https://leetcode.com/problems/pascals-triangle/solution/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/dynamic_programming/pascals-triangle.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.