动态规划 递推规划
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
public int fun(int[][] triangle){
if (triangle.length == 0){
return 0;
}
if(triangle.length == 1){
return triangle[0][0];
}
int[] result = new int[triangle.length];
result[0] = triangle[0][0];
for(int i = 1;i<triangle.length;i++){
result[i] = result[i-1]+triangle[i][i];
for(int j = i-1;j>0;j--){
result[j] = Math.min(result[j],result[j-1])+triangle[i][j];
}
result[0] = result[0]+triangle[i][0];
}
int min = result[0];
for(int t:result){
if(t<min){
min = t;
}
}
return min;
}
@Test
public void addition_isCorrect() {
int[][] input = new int[][]{{2},{3,4},{6,5,7},{4,1,8,3}};
System.out.println(fun(input));
}
