leetcode 120. 三角形最小路径和

题目描述：

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

例如，给定三角形：

[
     [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。

;

Popular Programs