Compute the Nth Row of a Pascal’s Triangle using Dynamic Programming Algorithm

Given an integer n, return the nth (0-indexed) row of Pascal’s triangle.

Pascal’s triangle can be created as follows: In the top row, there is an array of 1. Subsequent row is created by adding the number above and to the left with the number above and to the right, treating empty elements as 0.

The first few rows are:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Example 1
Input
n = 3
Output
[1, 3, 3, 1]
Explanation
This is row 3 in
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]

Compute the Pascal’s Triangle

We can calculate the values at Pascal’s Triangle using Dynamic Programming Algorithm. The value at p[i][j] equals p[i – 1][j] + p[i – 1][j – 1]. Thus, we can iteratedly updating the row (the size can be determined beforehand).

1
2
3
4
5
6
7
8
9
10

vector<int> solve(int n) {
    vector<int> res(n + 1, 0);
    res[0] = 1;
    for (int i = 0; i <= n; ++ i) {
        for (int j = i; j > 0; -- j) {
            res[j] += res[j - 1];
        }
    }
    return res;
}

vector<int> solve(int n) {
    vector<int> res(n + 1, 0);
    res[0] = 1;
    for (int i = 0; i <= n; ++ i) {
        for (int j = i; j > 0; -- j) {
            res[j] += res[j - 1];
        }
    }
    return res;
}

The time complexity is O(N^2) and the space complexity is O(N).

Pascal Triangle Implementations:

• Teaching Kids Programming – Pascal Triangle Algorithms and Applications
• Coding Exercise – Pascal Triangle II – C++ and Python Solution
• How to Print Pascal Triangle in C++ (with Source Code)
• Compute the Nth Row of a Pascal’s Triangle using Dynamic Programming Algorithm
• GoLang: Generate a Pascal Triangle

–EOF (The Ultimate Computing & Technology Blog) —