Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
思路：动态规划经典题。
解法一：动态规划顺推解法
1 int minimumTotal(vector<vector<int>>& T) { 2 int r = T.size(); 3 if (r == 0) return 0; 4 vector<vector<int>> dp(r, vector<int>(r, 0)); 5 dp[0][0] = T[0][0]; 6 for (int i = 1; i < r; ++i) { 7 for (int j = 0; j <= i; ++j) { 8 if (j == 0) dp[i][j] = dp[i - 1][j] + T[i][j]; 9 else if (j == i) dp[i][j] = dp[i - 1][j - 1] + T[i][j]; 10 else dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + T[i][j]; 11 } 12 } 13 int minimum = dp[r - 1][0]; 14 for (int j = 1; j < r; ++j) 15 minimum = min(minimum, dp[r - 1][j]); 16 return minimum; 17 }
时间复杂度：$O(n^2)$，空间复杂度：$O(n^2)$
解法二：动态规划逆推解法
1 int minimumTotal(vector<vector<int>>& T) { 2 int len = (T.size() > 0 ? T.size() : 0); 3 if (len == 0) return 0; 4 vector<int> dp(len, 0); 5 for (int j = 0; j < len; ++j) dp[j] = T[len - 1][j]; 6 for (int i = len - 2; i >= 0; --i) { 7 for (int j = 0; j <= i; ++j) { 8 dp[j] = min(dp[j], dp[j + 1]) + T[i][j]; 9 } 10 } 11 return dp[0]; 12 }
时间复杂度：$O(n^2)$，空间复杂度：$O(n)$
原文：https://www.cnblogs.com/qinduanyinghua/p/13205556.html