原题网址:https://www.lintcode.com/zh-cn/problem/triangle/
描述
给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
如果你只用额外空间复杂度O(n)的条件下完成可以获得加分,其中n是数字三角形的总行数。
样例
比如,给出下列数字三角形:
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。
则dp【i】【j】为上一行的同列和前一列路径和小的加上triangle【i】【j】,即dp【i】【j】=min(dp【i-1】【j】,dp【i-1】【j-1】)+triangle【i】【j】。
初始dp【0】【0】=triangle【0】【0】。
关于防止数组下标越界问题:转自此博客
//要取dp[i-1][j-1],和dp[i-1][j],但是要保证不越界。
//第i-1行的j的取值范围为[0, i-1]
int lo = max(0, j-1);//当j-1小于0的时候只取0,大于等于0的时候取自身。
int hi = min(j, i-1);//当j大于i-1的时候只取i-1,小于等于i-1的时候取自身。
代码:
int minimumTotal(vector<vector<int>> &triangle)
{
int n=triangle.size();
if (n==0)
{
return 0;
}
vector<vector<int>> dp(n,vector<int>(n,0));
dp[0][0]=triangle[0][0];
for (int i=1;i<n;i++)
{
for (int j=0;j<=i;j++)
{
//防止访问上一行时列下标越界;
//第i-1行j的取值范围为0~i-1;
int lo=max(0,j-1); //lo最小值为0;
int hi=min(j,i-1); //hi最大值为i-1;
dp[i][j]=min(dp[i-1][lo],dp[i-1][hi])+triangle[i][j];
}
}
int result=dp[n-1][0];
for (int i=1;i<n;i++)
{
if (dp[n-1][i]<result)
{
result=dp[n-1][i];
}
}
return result;
}
如果只用额外空间复杂度O(n),可把行信息去掉,定义一维数组dp[n],dp[j] 表示遍历到第 i 行时,三角形中第 i 行第 j 列处为终点的最小路径和。
状态转移方程为 dp[j] = min(dp[j] (上一行)+ dp[j-1](上一行))+ triangle[i][j]。
注意根据状态方程更新数据时要考虑覆盖问题:如果对列从前往后遍历,则上一行相应dp值被当前行dp值覆盖,影响下一列的计算,所以应从后往前遍历。可参考 此博客 及 背包问题 。
遍历完三角形后,dp[n]中存放的是从顶点到最后一行各点的最小路径和,找出其中的最小值return出去即可。
AC代码:
class Solution {
public:
/**
* @param triangle: a list of lists of integers
* @return: An integer, minimum path sum
*/
int minimumTotal(vector<vector<int>> &triangle) {
// write your code here
int n=triangle.size();
if (n==0)
{
return 0;
}
vector<int> dp(n,0);
dp[0]=triangle[0][0];
for (int i=1;i<n;i++)
{
for(int j=i;j>=0;j--) //注意这里的顺序,如果从前向后遍历将覆盖上一行相应位置的最短路径,所以应该从后向前遍历;
{
//防止访问上一行时列下标越界;
int lo=max(0,j-1); //lo最小值为0;
int hi=min(j,i-1); //hi最大值为i-1;
dp[j]=min(dp[lo],dp[hi])+triangle[i][j];
}
}
int result=dp[0];
for (int i=1;i<n;i++)
{
if (dp[i]<result)
{
result=dp[i];
}
}
return result;
}
};
其它参考:
https://blog.csdn.net/this_is_qiqi/article/details/78388888
此外,本题还可以从底向顶遍历,找出最小路径和,且不用担心下标越界问题,太狠了……参考 LintCode-数字三角形 。
思路:从二维数组的倒数第二行开始往上,每一行的元素改为下一行能与之相加的两个数较小者与其相加之后的和,如题中给出的例子,步骤为:
[ [ [
[2], [2], [11]
[3,4], → [9,10] → ]
[7,6,10] ]
]
AC代码:
class Solution {
public:
/**
* @param triangle: a list of lists of integers
* @return: An integer, minimum path sum
*/
int minimumTotal(vector<vector<int>> &triangle) {
// write your code here
int n=triangle.size();
if (n==0)
{
return 0;
}
//从底往上,把每一行的元素改为其下一行能与之相加的两个数得到的和的最小值;
for (int i=n-2;i>=0;i--)
{
for (int j=0;j<=i;j++)
{
int minSum=min(triangle[i+1][j],triangle[i+1][j+1])+triangle[i][j];
triangle[i][j]=minSum;
}
}
return triangle[0][0];
}
};
把自己最初思考的错误版本也放上来。
最初想的是定义dp[n],每一个dp元素表示到达当前行的最小路径和,另外使用一个int型变量 j 记录上一行列信息,但是如果上一行的三角形中有多个重复的最小元素时就无法解决了……对动态规划问题理解的还是不够透彻。
int minimumTotal(vector<vector<int>> &triangle)
{
int n=triangle.size();
vector<int> dp(n,0);
dp[0]=triangle[0][0];
int j=0;//上一行最小元素所在列;
//某行最小元素有多个怎么办?;
for (int i=1;i<n;i++)
{
int temp;
if (triangle[i][j]<triangle[i][j+1])
{
temp=triangle[i][j];
}
else
{
temp=triangle[i][j+1];
j=j+1;
}
dp[i]+=temp;
}
return dp[n-1];
}