Triangle
Total Accepted: 17536 Total Submissions: 65508My Submissions
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：dfs + 备忘录
在第i行的第j个位置，往下有两种走法的选择，往第i +1行的第j个位置或第j+1位置
在第i+1行的第j个位置或第j+1个位置的子问题与原问题相同，可用dfs递归求解
用一个数组_min[i][j]保存求解过程的值，避免重复计算。
复杂度：时间O(n ^2)，空间O(n^2)
思路2：dp + 滚动数组
设dp[i][j] 表示到达第i行第j个位置的路径的最小数值，则状态转移方程为
dp[i][j] = min(dp[i-1][k]) + A[i][j] 其中 dp[i-1][k]表示可到达dp[i][j]状态的上一个状态
在这里 k可以取 j -1 或 j，A[i][j]表示这个位置的值
因为在第i行只需要用到第i-1行的数据所以可以不用保存i-1前面的最优值。
最后只要用到数组 dp[j] 就可以
复杂度：时间O(n^2)，空间O(n)
//思路1
vector
> _min, _triangle;
int dfs(int i, int j){
if(i == _triangle.size() - 1){
return _triangle[i][j];
}
if(j < 0 || j >= _triangle[i].size()) return INT_MAX;
if(_min[i][j] != INT_MAX) return _min[i][j]; //某个特殊值表示 dfs(i,j)还没被计算过
return _min[i][j] = min(dfs(i + 1, j), dfs(i + 1, j + 1)) + _triangle[i][j];
}
int minimumTotal(vector
> &triangle) { if(triangle.empty()) return 0; _triangle = triangle; _min = vector
>(triangle.size(), vector
(triangle[triangle.size() - 1].size(), INT_MAX)); return dfs(0, 0); } //思路2 int minimumTotal(vector
> &triangle) { if(triangle.empty()) return 0; vector
dp(triangle.back().size(), 0); //初始化 int i = 0; for_each(triangle[0].begin(), triangle[0].end(),[&i, &dp](int &v){ dp[i++] = v; }); //迭代更新dp for(i = 1; i < triangle.size(); ++i){ int dp_j_1 = dp[0]; for(int j = 0; j < triangle[i].size(); ++j){ int tem = dp[j]; if(j == triangle[i].size() - 1) dp[j] = dp_j_1; dp[j] = min(dp_j_1 ,dp[j]) + triangle[i][j]; dp_j_1 = tem; } } int _min = INT_MAX; for(int j = 0; j < dp.size(); ++j) _min = min(_min, dp[j]); return _min; }