> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/05-31-2022-118.-pascals-triangle.md).

# 05/31/2022 118. Pascal's Triangle

Method: use DP. Each current row's value depends on the previous row's value. The base case is the first row is only 1. Then we iterate from rowIndex = 1 to numRows, we initiate a currentRow and get the prevRow list. First, the first element of each row is always 1. Then we start from index j = 1 to the rowIndex, we update by row\.add(prevRow\.get(j-1) + prevRow\.get(j)); Then the last element of each row is always 1 too.

Time O(N^2) N is the numRows.

Space O(1)

```
// Some code
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> rowFirst = new ArrayList<>();
        rowFirst.add(1);
        result.add(rowFirst);
        if (numRows == 1) return result;
        for (int rowIndex = 1; i < numRows; i++){
            List<Integer> row = new ArrayList<>();
            row.add(1);
            List<Integer> prevRow = result.get(rowIndex - 1);
            for (int j = 1; j < rowIndex; j++){//or you can use j < preRow.size()
                row.add(prevRow.get(j-1) + prevRow.get(j));
            }

            row.add(1);
            result.add(row);    
        }
        return result;
    }
}
```