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.
求出最小的路径。
第一次做使用递归，超时了。
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {int len = triangle.size();
int result = triangle.get(0).get(0);
result = getResult(result,0,0,triangle);
return result;
}
public static int getResult(int result,int pos,int num,List<List<Integer>> triangle){
if( num == triangle.size()-1 )
return result;
int num1 = triangle.get(num+1).get(pos);
int ans = result;
ans += num1;
ans = getResult(ans,pos,num+1,triangle);
num1 = triangle.get(num+1).get(pos+1);
result += num1;
result = getResult(result,pos+1,num+1,triangle);
return ans>result?result:ans;
}
}
所以还是需要用DP。
比较简单的DP应用。
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int height = triangle.size();
int[] dp = new int[height];
dp[0] = dp[0]+triangle.get(0).get(0);
for( int i = 1;i<height;i++){
int a = dp[0],b = dp[1];
dp[0] = dp[0]+triangle.get(i).get(0);
for( int j = 1;j<i;j++){
dp[j] = Math.min(a,b)+triangle.get(i).get(j);
a = b;
b = dp[j+1];
}
dp[i] = a+triangle.get(i).get(i);
}
int result = dp[0];
for( int i = 1;i<height;i++)
result = Math.min(result,dp[i]);
return result;
}
}