题解 | #三角形#

// [20],
// [30,40],
// [60,50,70],
// [40,10,80,30]]
//状态：F（i，j）从（0，0）到（i，j）的路径和
//转移方程：
        // if(j==0):F(i,j)=F(i-1,j)+arr[i][j]
        // else if(i==j):F(i,j)=F(i-1,j-1)+arr[i][j]
        // else:F(i,j)=min(F(i-1,j),F(i-1,j-1))+arr[i][j]
//初始值:f(0,0)=arr[0][0]
//返回结果:min(F(row-1),j)
class Solution {
public:
    int minimumTotal(vector<vector<int> >& triangle) {
        if(triangle.empty())
            return 0;
        int row=triangle.size();
        for(int i=1;i<row;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(j==0)
                {
                    triangle[i][j]=triangle[i-1][j]+triangle[i][j];
                }
                else if(j==i)
                {
                    triangle[i][j]=triangle[i-1][j-1]+triangle[i][j];
                }
                else 
                {
                    triangle[i][j]=
                    min(triangle[i-1][j-1],triangle[i-1][j])+triangle[i][j];
                }
            }
        }
        int _min=triangle[row-1][0];
        for(int j=1;j<triangle[row-1].size();j++)
        {
            _min=min(_min,triangle[row-1][j]);
        }
        return _min;
    }
};