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.
1、最简单的方法，通过递归求解，不过超时
class Solution{
public:
void dfs(int row,int col,vector
> &triangle,int sum,int &minT){
if(row>=triangle.size()-1){
minT=minT>sum sum:minT;
return;
}
dfs(row+1,col,triangle,sum+triangle[row+1][col],minT);
dfs(row+1,col+1,triangle,sum+triangle[row+1][col+1],minT);
}
int minimumTotal(vector
> &triangle){ if(!triangle.size())return 0; int minT=INT_MAX; dfs(0,0,triangle,triangle[0][0],minT); return minT; } };
2、可以尝试递归+纪录路径的方法，不知道时间超不超时，不过空间复杂度要比O（n）多了；
3、动态规划，设dp[row][col]代表dao第row行第col列的最小值，则有dp[row][col]=min{dp[row-1][col-1],dp[row-1][col]}+triangle[row][col];AC了，但空间复杂度大于O(n)
class Solution{
public:
int minimumTotal(vector
> &triangle){
if(!triangle.size())return 0;
vector
> dp(triangle); int minT=INT_MAX; dp[0][0]=triangle[0][0]; for(int i=1;i
4、动态规划，根据3可以将二维数组变为一维数组来处理，但是j就不能从0开始遍历了，得从后向前遍历
class Solution{
public:
int minimumTotal(vector
> &triangle){
if(!triangle.size())return 0;
vector
dp(triangle.size()); int minT=INT_MAX; dp[0]=triangle[0][0]; for(int i=1;i
=0;j--){ if(j==0)dp[j]+=triangle[i][j]; else if(j==i)dp[j]=dp[j-1]+triangle[i][j]; else dp[j]=min(dp[j],dp[j-1])+triangle[i][j]; } } for(int i=0;i