120. Triangle（动态规划两种解法，空间优化）

1. Triangle

   Medium

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[

[2],

[3,4],

[6,5,7],

[4,1,8,3]

]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

空间复杂度O(n^2)：

int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size()==0) return 0;
        int n=triangle.size();
        int dp[n][n]; dp[0][0]=triangle[0][0];
        for(int i=1;i<n;i++) dp[i][0]=dp[i-1][0]+triangle[i][0], dp[i][i]=dp[i-1][i-1]+triangle[i][i];
        for(int i=1;i<n;i++)
            for(int j=1;j<i;j++)
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
        int ans=INT_MAX;
        for(int i=0;i<n;i++)
            ans=min(dp[n-1][i],ans);
        return ans;
    }
           

注意到这一段代码中

dp[i][j]=min(dp[i-1][j-1],dp[i-1])

实际上dp[i][j]只与上一行i-1有关，故可以直接利用上一行的数据更新第i行，dp数组可以优化成一维数组。

由于

dp[i][j]=min(dp[i-1][j-1],dp[i-1])

等式右边的dp[j-1],dp[j]是第i-1行的数据。

如果顺序遍历 j 的话，则在更新dp[j]之前dp[j-1]已经被更新了，再用到

dp[i][j]=min(dp[i-1][j-1],dp[i-1])

这个等式的时候，dp[j-1]已经更新成当前行的dp[j-1]了，所以要对 j 逆序遍历。

空间复杂度O(n)：

int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size()==0) return 0;
        int n=triangle.size();
        int dp[n]; dp[0]=triangle[0][0];
        for(int i=1;i<n;i++)
        {
            for(int j=i;j>=0;j--)//注意这里需要逆序遍历
            {
                if(j==i) dp[j]=dp[j-1]+triangle[i][j];
                else if(j==0) dp[j]=dp[j]+triangle[i][j];
                else dp[j]=min(dp[j-1],dp[j])+triangle[i][j];
            }
        }
        int ans=INT_MAX;
        for(int i=0;i<n;i++)
            ans=min(ans,dp[i]);
        return ans;
    }