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:
d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] represents the minimum path sum of row i i i and column j j j .
State Analysis:
d p [ 0 ] [ 0 ] = c [ 0 ] [ 0 ] dp[0][0]=c[0][0] d p [ 0 ] [ 0 ] = c [ 0 ] [ 0 ]
The State Transfer Equation:
d p [ i ] [ j ] = { d p [ i − 1 ] [ 0 ] + c [ i ] [ 0 ] j = 0 d p [ i − 1 ] [ i − 1 ] + c [ i ] [ i ] j = = i m i n ( d p [ i − 1 ] [ j − 1 ] , d p [ i − 1 ] [ j ] ) + c [ i ] [ j ] 0 < j < i 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}
d p [ i ] [ j ] = ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ d p [ i − 1 ] [ 0 ] + c [ i ] [ 0 ] d p [ i − 1 ] [ i − 1 ] + c [ i ] [ i ] m i n ( d p [ i − 1 ] [ j − 1 ] , d p [ i − 1 ] [ j ] ) + c [ i ] [ j ] j = 0 j = = i 0 < j < i
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, d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] is only relevant to d p [ i − 1 ] [ j ] dp[i-1][j] d p [ i − 1 ] [ j ] , but d p [ i − 2 ] [ j ] dp[i-2][j] d p [ i − 2 ] [ j ] and previous states are irrelevant, so we don’t have to store these states. We can only use extra O ( 2 n ) O(2n) O ( 2 n ) space: two one-dimensional arrays of length n n n for the transfer, and map i i i to one of the one-dimensional arrays according to the parity, then i − 1 i-1 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 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 j j j decreasingly from i i i to 0 0 0 , so that we only need a one-dimensional array d p dp d p of length n n n to complete the state transition.
d p [ j ] = m i n ( d p [ j − 1 ] , d p [ j ] ) + c [ i ] [ j ] dp[j] = min(dp[j-1], dp[j]) + c[i][j]
d p [ j ] = m i n ( d p [ j − 1 ] , d p [ 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 ( n 2 ) O(n^2) O ( n 2 ) .
Space Complexity : O ( n ) O(n) O ( n ) .
Bottom-Up Approach
The state transfer equation of bottom-up approach is:
d p [ i ] [ j ] = m i n ( d p [ i + 1 ] [ j ] , d p [ i + 1 ] [ j + 1 ] ) + c [ i ] [ j ] dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + c[i][j] d p [ i ] [ j ] = m i n ( d p [ i + 1 ] [ j ] , d p [ 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 ( n 2 ) O(n^2) O ( n 2 ) .
Space Complexity : O ( n ) 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 . 😉😃💗