題目

?解答：

直接按照空間復雜度O(n)來做了。這種明顯是動態規劃，每一層用到上一層的信息。

觀察數據形狀，如下：

(0,0)

(1,0)(1,1)

(2,0)(2,1)(2,2)

(3,0)(3,1)(3,2)(3,3)

...

(n-1,0)...(n-1,n-1)

設dp[n],定義為本層第n個數據的最小路徑

特殊的兩處：(i,j):j=0和j=i

對j=0，dp[0]為(i-1,0)的dp[0]與本層的(i,0)相加

對j=i，dp[j]為(i-1,i-1)的dp[i-1]與本層的(i,i)相加

其余的，0<j<i,dp[j]為上一層的dp[j]與dp[j-1]的最小值，加上本層的(i,j)值

綜上三條，每一層的循環應該是從右向左，從大下標到小下標。

遍歷n層，最后找到最后一層的最小值輸出即可。

class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {int n = triangle.size();//j=0   dp[i][0]=triangle[i][j]+dp[i-1][0]//0<j<i   dp[i][j]=triangle[i][j]+min(dp[i-1][j],dp[i-1][j-1])//j=i   dp[i][i]=triangle[i][i]+dp[i-1][i-1]vector<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[j][j];else if(j!=0)dp[j]=triangle[i][j]+min(dp[j],dp[j-1]);else dp[j]=dp[j]+triangle[i][0];}}int ans = dp[0];for(int i=1;i<n;i++)if(dp[i]<ans) ans=dp[i];return ans;}
};

時間復雜度O(n*n)

空間復雜度O(n)