题目描述:
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如,给定三角形:
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
自顶向下的最小路径和为 11
(即,2 + 3 + 5 + 1 = 11)。
说明:
如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。
思路:
最容易想到的就是动态规划,用数组构建一个三角形,同步记录从顶部往下走,到达每个位置的最小值,然后在最后一行中找出问题的解。代码如下:
int minimumTotal(vector<vector<int>>& triangle) {
int m=triangle.size();
if(m==0) return 0;
//动态规划 1:构建一个三角形,记录每个位置的可能路径的最小值
int dp[m][m]={0};
//每个元素只能走到它的下方或者右下方
//也就是每个元素只能来自它的上方或者左上方
//注意特殊情况:左腰上的元素,只能来自它的上方;右腰只能从左上方来。
dp[0][0]=triangle[0][0];
//左腰
for(int i=1;i<m;i++)
dp[i][0]=triangle[i][0]+dp[i-1][0];
//右腰
for(int i=1;i<m;i++)
dp[i][i]=triangle[i][i]+dp[i-1][i-1];
//其他位置
for(int i=1;i<m;i++)
for(int j=1;j<i;j++)
dp[i][j]=triangle[i][j]+min(dp[i-1][j-1], dp[i-1][j]);
//找出最小值
int ans=dp[m-1][0];
for(int i=1;i<m;i++)
ans=min(ans,dp[m-1][i]);
return ans;
}
时间复杂度O(n^2),空间复杂度O(n^2),测试运行时间30ms。
注意递推式:dp[ i ][ j ] = triangle[ i ] [ j ]+min(dp[ i-1 ][ j-1 ], dp[ i-1 ][ j ]),可以把dp[ i ][ j ] 看作 dp[ j ],d[ i-1 ][ j ]看作它被覆盖前的值。这样我们就能把空间优化到O(n)了。由于dp[ i-1 ][ j ]参与了运算,为了避免它被覆盖掉,有两种做法:1,用一个临时变量保存它,用于后续计算;2,从后往前计算,数据覆盖也是从后往前的,由于dp[j-1]的计算与dp[ j ]没关系,所以不需要关注dp[ j ]。代码如下:
int minimumTotal(vector<vector<int>>& triangle) {
int m=triangle.size();
if(m==0) return 0;
//动态规划 2:只用一行虚构一个三角形
int dp[m]={0};
//每个元素只能走到它的下方或者右下方
//也就是每个元素只能来自它的上方或者左上方
//注意特殊情况:左腰上的元素,只能来自它的上方;右腰只能从左上方来。
dp[0]=triangle[0][0];
for(int i=1;i<m;i++)
{
//为了避免数据覆盖,从后往前填充
//每行的最后一个元素
dp[i]=triangle[i][i]+dp[i-1];
//中间元素
for(int j=i-1;j>0;j--)
dp[j]=triangle[i][j]+min(dp[j-1],dp[j]);
//第一个元素
dp[0]+=triangle[i][0];
}
int ans=dp[0];
for(int i=1;i<m;i++)
ans=min(dp[i],ans);
return ans;
}
时间复杂度不变,空间复杂度降低到O(n),测试运行时间 4 ms。
这是从上往下走的做法,还可以从下往上走:
int minimumTotal(vector<vector<int>>& triangle) {
int m=triangle.size();
if(m==0) return 0;
//从最后一行往上一行走,路径信息直接保存到三角形中
for(int i=m-2;i>=0;i--)
for(int j=0;j<=i;j++)
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
return triangle[0][0];
}
代码简短了很多!由于从下往上走时,对于所有的元素都有相同的两种可能:从下边的位置上来,或者从右下的位置上来。这样就不用把双腰上的元素特殊处理了。时间复杂度仍旧是O(n^2),而空间复杂度看似降低到了O(1),不过我认为它破坏了原有的数据,应该先拷贝一份数据再进行计算。拷贝数据的话,空间复杂度也就是O(n^2)了。测试运行时间 4ms。
当然,同样可以用一维数组虚拟出一个三角形,把空间复杂度降低到O(n)。代码如下:
int minimumTotal(vector<vector<int>>& triangle) {
int m=triangle.size();
if(m==0) return 0;
int dp[m]={0};
//初值:最后一行的数据
for(int i=0;i<m;i++)
dp[i]=triangle[m-1][i];
//从最后一行开始往上走
for(int i=m-2;i>=0;i--)
for(int j=0;j<=i;j++)
dp[j]=triangle[i][j] + min(dp[j], dp[j+1]);
return dp[0];
}
只需要拷贝最后一行的元素即可! 测试运行时间 4ms。
;