---恢复内容开始---
简单的动态规划题，使用了二维dp数组就能很好的表示。
由于有边界的问题，所以这个dp数组为 dp[n+1][n+1]。
dp[i][j]意思是终点为(i-1,j-1)点的路径最小和。
我们需要把这个三角形变成方阵来看，先看看样例:
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
变成方阵之后就变成了
[
[2, INT_MAX,INT_MAX, INT_MAX],
[3, 4,INT_MAX, INT_MAX],
[6, 5, 7, INT_MAX],
[4, 1, 8, 3],
]
有上面方阵很容易得出这个状态转移方程为
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i-1][j-1];
为了避开数组越界(人i=0或j=0)的问题，我们的dp数组容量比triange大一：即triangle[i][j]->dp[i+1][j+1]
class Solution {
public:
int minimumTotal(vector<vector<int>> &triangle)
{
size_t n = triangle.size();
int dp[n + ][n + ];
memset(dp, 0x3f, sizeof(dp));
int ans = INT_MAX;
dp[][] = triangle[][];
for (size_t i = ; i <= n; i++)
{
for (size_t j = ; j <= triangle[i - ].size(); j++)
{
dp[i][j] = min(dp[i - ][j - ], dp[i - ][j]) + triangle[i-][j-];
}
}
for (size_t i = ; i <= n; i++)
{
ans = min(ans, dp[n][i]);
}
return ans;
}
};
或者根本不用再建立一个新的dp数组，而是直接在triangle数组上进行操作。比如
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.size() == || triangle[].size() == ) return ;
int n = triangle.size();
for(int i = n - ; i >= ; i--)
for(int j = ; j < i + ; j++)
triangle[i][j] += min(triangle[i+][j], triangle[i+][j+]);
return triangle[][];
}
};
这一题的升级版问题可以看我的另一篇随笔: 下降路径最小和