计算三角矩阵的最小路径长（动态规划）（c++，每日一练）

￡神魔★判官ぃ 2022-12-01 14:19 113阅读 0赞

## 题目描述 ##

给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，

例如，给出的三角形如下：

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

最小的从顶部到底部的路径和是2 + 3 + 5 + 1 = 11。注意：

如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。

经典动态规划题，把每个点的最小路径求出来，最后求出总的最小路径即可。

class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            if(triangle.empty())
                return 0;
            vector<vector<int>>a=triangle;
            for(int i=1;i<a.size();i++){
                for(int j=0;j<a[i].size();j++){
                    if(j==0)
                        a[i][0]=a[i-1][0]+a[i][0];
                    else if(j==i)
                        a[i][j]=a[i-1][j-1]+a[i][j];
                    else{
                        a[i][j]=min(a[i-1][j],a[i-1][j-1])+a[i][j];
                    }
                }
            }
            int minsum=a[a.size()-1][0];
            for(int i=1;i<a[a.size()-1].size();i++)
            {
                minsum=min(minsum,a[a.size()-1][i]);
            }
            return minsum;
        }
    };

还有一种思路，从底层向上求最小路径，代码大大简化，没有那么多过程。

class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            vector<vector<int>>a=triangle;
            for(int i=a.size()-2;i>=0;i--)
            {
                for(int j=a[i].size()-1;j>=0;j--)
                {
                    a[i][j]=min(a[i+1][j],a[i+1][j+1])+a[i][j];
                }
            }
            return a[0][0];
        }
    };