02(120三角形最小路径和) 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标+1的两个结点。示例[[2],[3,4],[6,5,7],[4,1,8,3]]自顶向下的最小路径和为11（即，2+3+5+1=11）。说明：如果你可以只使用O(n)的额外空间（n为三角形的总行数）来解决这个问题，那么你的算法会很加分。///MemorySearch///TimeComplexity:O(n^2)///SpaceComplexity:O(1)classSolution{public:intminimumTotal(vector<vector<int>>&triangle){intn=triangle.size();vector<vector<int>>dp(n,vector<int>(n,-1));for(inti=0;i<n;i++)go(triangle,n-1,i,dp);return*min_element(dp[n-1].begin(),dp[n-1].end());}private:intgo(constvector<vector<int>>&triangle,inti,intj,vector<vector<int>>&dp){if(dp[i][j]!=-1)returndp[i][j];if(i==0)returndp[i][j]=triangle[i][j];if(j==0)returndp[i][j]=triangle[i][j]+go(triangle,i-1,0,dp);if(j==i)returndp[i][j]=triangle[i][j]+go(triangle,i-1,i-1,dp);returndp[i][j]=triangle[i][j]+min(go(triangle,i-1,j-1,dp),go(triangle,i-1,j,dp));}};///DynamicProgramming///TimeComplexity:O(n^2)///SpaceComplexity:O(1)classSolution{public:intminimumTotal(vector<vector<int>>&triangle){intn=triangle.size();for(inti=1;i<n;i++){triangle[i][0]+=triangle[i-1][0];triangle[i][i]+=triangle[i-1][i-1];for(intj=1;j<i;j++)triangle[i][j]+=min(triangle[i-1][j-1],triangle[i-1][j]);}return*min_element(triangle[n-1].begin(),triangle[n-1].end());}};
来自：动态规划算法-动态规划算法
