LeetCode 120. Triangle

刺骨的言语ヽ痛彻心扉 2022-05-08 01:20 192阅读 0赞

#### 动态规划 问题120. Triangle ####

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) 空间复杂度O(n^2)

class Solution {
        
    public:
        
        int helper(vector<vector<int>>& triangle,int x,int y,vector<vector<int>>& dp) {
        
            int n = triangle.size();
            if(x>=n||y>=n) return 0;
            
            if(dp[x][y])
                return dp[x][y];
            else
                dp[x][y] = min(helper(triangle,x+1,y,dp),helper(triangle,x+1,y+1,dp)) + triangle[x][y];
            return dp[x][y];
            
        }
        
        int minimumTotal(vector<vector<int>>& triangle) {
        
            int n = triangle.size();
            if(!n) return 0;
            
            vector<vector<int>> dp(n,vector<int>(n,0));
            int res = helper(triangle,0,0,dp);
            return res;
        }
    };

#### 自底向上优化空间到o(n) ####

class Solution {
        
    public:
        
        int helper(vector<vector<int>>& triangle,int x,int y,vector<int>& dp) {
        
            int n = triangle.size();
            if(x>=n||y>=n) return 0;
            for(int i=0;i<n;++i)
                dp[i] = triangle[n-1][i];
            
            for(int i=n-2;i>=0;--i) {
        
                for(int j=0;j<=i;++j) {
        
                    dp[j] = min(dp[j],dp[j+1]) + triangle[i][j];
                }
            }
            
            return dp[0];
            
        }
        
        int minimumTotal(vector<vector<int>>& triangle) {
        
            int n = triangle.size();
            if(!n) return 0;
            
            vector<int> dp(n,0);
            int res = helper(triangle,0,0,dp);
            return res;
        }
    };