题目描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
Example 1:
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
Example 2:
输入：triangle = [[-10]] 输出：-10
Constraints:
- 1 <= triangle.length <= 200
- triangle[0].length == 1
- triangle[i].length == triangle[i - 1].length + 1
- -10^4 <= triangle[i][j] <= 10^4
解题思路
- dp思想，后面的状态由前面的状态所转移，并且转移后不受前面状态的影响
- 想一想，当j = 0时，从第二行开始，只能由上一行的正上方所转移
- 当j = i时，只能由上一行的左上方所转移
- 遍历最后一行的dp[n - 1][j]，得最小值就是结果。
如何确定一道题目是否可以用 DP 解决，我们要从有无后效性进行分析。首先，既然是从上到下的路径，那么最后一个点必然是落在最后一行。对于最后一行的某个位置的值，根据题意只能从上一行的某一个位置或者某两个位置之一转移而来。同时，我们只关注前一位的累加值是多少，而不关心这个累加值结果是由什么路径而来的。这显然就满足了「无后效性」的定义：我们转移某个状态需要用到某个值，但是并不关心该值是如何而来的。更加的学术表达是：当前某个状态确定后，之后的状态转移与之前的决策无关 因此我们可以确定使用 DP 进行求解。接下来的问题是，我们该如何确定「状态定义」呢？通常我们会根据「结尾」或「答案」来猜 DP 的状态定义。所谓的「结尾」通常就是指「最后一步」。
C++代码
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int row = triangle.size();
int col = triangle[row - 1].size();
vector<vector<int>> dp(row, vector<int>(col, 0));
dp[0][0] = triangle[0][0];
for(int i = 1; i < row; i++){
for(int j = 0; j < i + 1; j++){
if(j == 0){
dp[i][j] = dp[i - 1][j] + triangle[i][j];
}else if(j == i){
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 res = INT_MAX;
for(int i = 0; i < col; i++){
res = min(res, dp[row - 1][i]);
}
return res;
}
};
