题目
120. 三角形最小路径和
题目解释
如下图所示：
圆中的数字j表示该圆对应的列数
则triangle[i][j] 表示第I行第j列元素值
自上而下出发：从(i,j)向下走，两种情况：
(I+1,j) 或者 (i+1,j+1) 的位置
Q:求从上到下的最小路径
思路
动态规划
定义状态转移方程
dp[i][j]: 在第i行第j列时的最小路径
状态转移方程
当前最小路径 = 上一层的最小路径 + 当前路径值
则求上一次路径的最小值，即求上次选择的哪个一个位置
对于现在的位置(i,j)，上一个位置在哪与现位置的列坐标j有关，对现位置进行分类讨论
i) 现位置在左边界时，即j == 0
只能由第i-1行的在左边界的位置来，上一位置坐标为(i-1,j)
则dp[i][j] = dp[i - 1][j] + triangle[I][j]
ii）现位置在右边界时，即j == triangle[I].size()
只能由第i-1行的在右边界的位置来，上一位置坐标为(i-1,j-1)
则dp[i][j] = dp[i - 1][j - 1] + triangle[I][j]
iii）现位置在中间的情况
可由（i-1,j）或者（i-1,j-1）到（i,j），选择哪一个位置是取决于哪个的路径值更小
则dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
最后到达在终点行，得到所有不同走法的总路径，找最小总路径
初始化
三角形的顶点元素
dp[0][0] = triangle[0][0]
AC代码
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
int dp[n][n];
dp[0][0] = triangle[0][0];
for(int i = 1; i < n; i++) {
int m = triangle[i].size();
for(int j = 0; j < m; j++) {
if(j == 0)
dp[i][j] = dp[i - 1][j] + triangle[i][j];
else if(j == m - 1)
dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
else
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
}
}
int Min = dp[n - 1][0];
for(int i = 1; i < n; i++)
Min = min(Min, dp[n - 1][i]);
return Min;
}
};