leetcode 120. 三角形最小路径和

题目描述:

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11(即,3 + 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。

;