三角形最短路径和

1.动态规划求解

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
题目链接

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for(int i=1;i<triangle.size();i++)
        {
            for(int j=0;j<triangle[i].size();j++)
            {
                if(j==0)
                triangle[i][j]+=triangle[i-1][j];
                else if(j==triangle[i].size()-1)
                triangle[i][j]+=triangle[i-1][j-1];
                else
                triangle[i][j]+=fmin(triangle[i-1][j-1],triangle[i-1][j]);
            }
        }
        
        int sub=triangle.size()-1;//获取最后一行的坐标
        int sum=triangle[sub][0];
        for(int i=0;i<triangle[sub].size();i++)
        {
            sum=fmin(sum,triangle[sub][i]);
        }
        return sum;
    }
};

2.不破坏原始空间写法

上面的解法，我们直接利用了数组的空间，我们可以自己开辟一个二维数组，即不破坏原始的空间

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<vector<int>> ret(triangle.size(),vector<int>(triangle.size(),0));
        ret[0][0]=triangle[0][0];

        for(int i=1;i<triangle.size();i++)
        {
            for(int j=0;j<triangle[i].size();j++)
            {
                if(j==0)
                ret[i][j]=triangle[i][j]+ret[i-1][j];
                else if(j==triangle[i].size()-1)
                ret[i][j]=triangle[i][j]+ret[i-1][j-1];
                else
                ret[i][j]=triangle[i][j]+fmin(ret[i-1][j-1],ret[i-1][j]);
            }
        }
        
        int sub=triangle.size()-1;
        int sum=ret[sub][0];
        for(int i=0;i<triangle[sub].size();i++)
        {
            sum=fmin(sum,ret[sub][i]);
        }
        return sum;
    }
};

3.空间复杂度优化

第二种解法之中，空间复杂度为O(N^2)，而又dp[i][j]只与dp[i-1][j]和dp[i-1][j-1]有关系，即当前行只与上一行有关系，因此可以定义一个一维数组重复使用，为了避免数据被覆盖的问题，我们从后往前遍历每一行

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> ret(triangle.size(),0);
        ret[0]=triangle[0][0];
        for(int i=1;i<triangle.size();i++)
        {
            for(int j=triangle[i].size()-1;j>=0;j--)//避免被覆盖，从后往前进行遍历
            {
                if(j==0)
                ret[j]+=triangle[i][j];
                else if(j==triangle[i].size()-1)
                ret[j]=triangle[i][j]+ret[j-1];
                else
                ret[j]=triangle[i][j]+fmin(ret[j],ret[j-1]);
            }
        }

        int min=ret[0];
        for(int i=0;i<triangle.size();i++)
        {
            min=fmin(min,ret[i]);
        }
        return min;
    }
};

4.自低向上求解

上述的方法都是从上至下进行求解，因此最后还需要遍历一遍寻求最小值，如果从下至上求解，那么最后就只剩下一个最小值了

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {

        for(int i=triangle.size()-2;i>=0;i--)//从倒数第二行开始
        {
            for(int j=triangle[i].size()-1;j>=0;j--)
            {
                triangle[i][j]+=fmin(triangle[i+1][j],triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};