[C++] LeetCode 120. 三角形最小路徑和

題目

給出一個三角形（資料數組），找出從上往下的最小路徑和。每一步隻能移動到下一行中的相鄰結點上。

比如，給你如下三角形：

則從上至下最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）

注意：

加分項：如果你可以隻使用 O(n) 的額外空間（n是三角形的行數）。

題解

普通動态規劃題目，注意每一行左右兩端點隻有一種路徑，其他的都有兩種路徑。

代碼

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
        if(n==0) return 0;
        vector<int> dp(n,0);
        int tmp1=triangle[0][0];
        int minRes=INT_MAX;
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                int tmp=dp[j];
                if(i==0) dp[j]=tmp1;
                else if(j==0){
                    dp[j]=dp[j]+triangle[i][j];
                }
                else if(j==i){
                    dp[j]=tmp1+triangle[i][j];
                }
                else {
                    dp[j]=min(tmp1+triangle[i][j],dp[j]+triangle[i][j]);
                }
                tmp1=tmp;
                if(i==n-1) minRes=min(minRes,dp[j]);
            }
        }
        return minRes;
    }
};