Leetcode-120. 三角形最小路径和

发表于 分类于 阅读次数：

https://leetcode-cn.com/problems/triangle/

解法1：动态规划

题目要求O（n）的空间复杂度

所以我们要对状态转移方程进行压缩

我们首先写二维的状态转移方程dp[i][j]表示从第i行第j列走到底部要的路径和

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

现在我们对状态转移方程进行压缩

我们用一维的状态转移方程dp2[j]表示从当前行的j列走到底部要的路径和

我们发现可以将状态转移方程改写为dp[j]=min(dp[j],dp[j+1])+triangle[i][j];

我们从底部向上进行dp转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
        vector<int> dp(n,0);
        for(int i=n-1;i>=0;i--)
        {
            for(int j=0;j<triangle[i].size();j++)
            {
                if(i<n-1)
                    dp[j]=min(dp[j],dp[j+1])+triangle[i][j];
                else dp[j]+=triangle[i][j];
            }
        }
        return dp[0];
    }
};