题解 | #最小三角路径和#

知识点

多维路径动态规划

思路

我们可以考虑反向转移，dp[i][j]代表从最后一行到达第i行第j列的最小代价，dp[0][0]即为所求（注意下标从0开始）。

转移方程：由题意，当前位置dp[i][j],只能由dp[i+1][j]和dp[i+1][j+1]转移过来。还要再加上自身的花费:

dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+cows[i][j];

初始化：最后一行直接初始化为cows的最后一行

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型vector<vector<>> 
     * @return int整型
     */
    int minimumTotal(vector<vector<int> >& cows) {
        int dp[1005][1005];
        int n=cows.size();
        for(int i=0;i<n;i++)
        {
            dp[n-1][i]=cows[n-1][i];
        }
        for(int i=n-2;i>=0;i--)
        {
            for(int j=0;j<=i+1;j++)
            {
                dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+cows[i][j];
            }
        }
        cout<<dp[0][0]<<endl;
        return dp[0][0];
    }
};