[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
- State definition:
\(dp[i][j]\) represents the minimum path sum of row \(i\) and column \(j\).
- State Analysis:
\(dp[0][0]=c[0][0]\)
- The State Transfer Equation:
\[ dp[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 | public int minimumTotal(List<List<Integer>> triangle) { |
In fact, \(dp[i][j]\) is only relevant to \(dp[i-1][j]\), but \(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)\) space: two one-dimensional arrays of length \(n\) for the transfer, and map \(i\) to one of the one-dimensional arrays according to the parity, then \(i-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
23public 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 \(j\) decreasingly from \(i\) to \(0\), so that we only need a one-dimensional array \(dp\) of length \(n\) to complete the state transition.
\[ 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
23public 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(n^2)\).
- Space Complexity: \(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]\)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public 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(n^2)\).
- Space Complexity: \(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. 😉😃💗