By Long Luo

This article is the solution Math Intuition of Dynamic Programming: Shift One and Added of Problem 118. Pascal’s Triangle .

Intuition

To generate a Pascal’s triangle is as the below animated git shows.

We can find that the Current Layer has only one element more than the Previous Layer. The elements in the Current Layer are equal to the elements in the Previous Layer, which was added one by one after being shifted one bit backward.

Therefore, we only need to deal with the Last Layer. We add a \(0\) at the beginning and the end of the Last Layer. Then sum the corresponding positions to get a New Layer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> oneRow = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) {
                oneRow.add(1);
            } else {
                oneRow.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j));
            }
        }

        ans.add(oneRow);
    }

    return ans;
}

Analysis

• Time Complexity: \(O(n^2)\).
• Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗