[LeetCode][120. Triangle] Dynamic Programming: Top-Down and Bottom-Up Approach

By Long Luo

This article is the solution Dynamic Programming Space O(n) Solutions: Top-Down and Bottom-Up Approaches of Problem 120. Triangle.

Intuition

This problem is a classic and typical dynamic programming problem. We can break the large problem into sub-problems.

We can use both the Top-Down and Bottom-Up approach to solve this problem.

Top-Down Approach

  1. State definition:

dp[i][j]dp[i][j] represents the minimum path sum of row ii and column jj.

  1. State Analysis:

dp[0][0]=c[0][0]dp[0][0]=c[0][0]

  1. The State Transfer Equation:

dp[i][j]={dp[i1][0]+c[i][0]j=0dp[i1][i1]+c[i][i]j==imin(dp[i1][j1],dp[i1][j])+c[i][j]0<j<idp[i][j] = \begin{cases} dp[i-1][0] + c[i][0] & j=0 \\ dp[i-1][i-1] + c[i][i] & j==i \\ min(dp[i-1][j-1],dp[i-1][j]) + c[i][j] & 0 < j < i \\ \end{cases}

so we can easily write such code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return 0;
}

int len = triangle.size();
int[][] dp = new int[len][len];
dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < len; i++) {
dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
for (int j = 1; j < i; j++) {
dp[i][j] = Math.min(dp[i - 1][j - 1] + triangle.get(i).get(j), dp[i - 1][j] + triangle.get(i).get(j));
}
}

int min = dp[len - 1][0];
for (int i = 1; i < len; i++) {
min = Math.min(min, dp[len - 1][i]);
}

return min;
}

In fact, dp[i][j]dp[i][j] is only relevant to dp[i1][j]dp[i-1][j], but dp[i2][j]dp[i-2][j] and previous states are irrelevant, so we don’t have to store these states. We can only use extra O(2n)O(2n) space: two one-dimensional arrays of length nn for the transfer, and map ii to one of the one-dimensional arrays according to the parity, then i1i-1 is mapped to the other one-dimensional array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
int len = triangle.size();
int[][] dp = new int[2][len];

dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < len; i++) {
int cur = i % 2;
int prev = 1 - cur;

dp[cur][0] = dp[prev][0] + triangle.get(i).get(0);
dp[cur][i] = dp[prev][i - 1] + triangle.get(i).get(i);
for (int j = 1; j < i; j++) {
dp[cur][j] = Math.min(dp[prev][j - 1], dp[prev][j]) + triangle.get(i).get(j);
}
}

int min = dp[(len - 1) % 2][0];
for (int i = 1; i < len; i++) {
min = Math.min(min, dp[(len + 1) % 2][i]);
}

return min;
}

We enumerate jj decreasingly from ii to 00, so that we only need a one-dimensional array dpdp of length nn to complete the state transition.

dp[j]=min(dp[j1],dp[j])+c[i][j]dp[j] = min(dp[j-1], dp[j]) + c[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
int len = triangle.size();

int[] dp = new int[len];
dp[0] = triangle.get(0).get(0);

for (int i = 1; i < len; i++) {
dp[i] += dp[i - 1] + triangle.get(i).get(i);

for (int j = i - 1; j > 0; j--) {
dp[j] = Math.min(dp[j - 1], dp[j]) + triangle.get(i).get(j);
}

dp[0] += triangle.get(i).get(0);
}

int min = dp[0];
for (int i = 1; i < len; i++) {
min = Math.min(min, dp[i]);
}

return min;
}

Analysis

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

Bottom-Up Approach

The state transfer equation of bottom-up approach is:

dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+c[i][j]dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + c[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minimumTotal(List<List<Integer>> triangle) {
int len = triangle.size();

int[] dp = new int[len];

for (int i = 0; i < len; i++) {
dp[i] = triangle.get(len - 1).get(i);
}

for (int i = len - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}

return dp[0];
}

Analysis

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

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. 😉😃💗