Triangle: minimum path sum
思路:DP
- 状态表示:f[i][j] 表示第i行第j个数的 minimum path sum
- 状态计算:可以分为从triangle[i][j]左上方走,从triangle[i][j]右上方走
- 参考 :yxc
题目
/*
* @lc app=leetcode id=120 lang=cpp
*
* [120] Triangle
*
* https://leetcode.com/problems/triangle/description/
*
* algorithms
* Medium (40.33%)
* Likes: 1290
* Dislikes: 149
* Total Accepted: 197.5K
* Total Submissions: 486.5K
* Testcase Example: '[[2],[3,4],[6,5,7],[4,1,8,3]]'
*
* 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.
*
*/
代码
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
// 切入点:
// 状态表示:f[i][j] 表示第i行第j个数的 minimum path sum
// 状态计算:集合可以分为从triangle[i][j]左上方,从triangle[i][j]右上方
// 走到第i行第j个数结尾的minimum path sum
// 难点一: 如何用vector储存二维数组?
int n = triangle.size();
vector<vector<int>> f(n, vector<int>(n)); //这里确定j的范围是n
f[0][0] = triangle[0][0];
for (int i = 1; i < n; i ++ )
// 难点二: 如何确定j的范围?
for (int j = 0; j <= i; j ++ )
{
//难点三: 区分边界情况
f[i][j] = INT_MAX;
if (j > 0) f[i][j] = min(f[i][j], f[i - 1][j - 1] + triangle[i][j]);
if (j < i) f[i][j] = min(f[i][j], f[i - 1][j] + triangle[i][j]);
}
int res = INT_MAX;
for (int j = 0; j < n; j ++ )
res = min(res, f[n - 1][j]);
return res;
}
};