题目

 解答：

直接按照空间复杂度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)