动态规划 递推规划
给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
[ [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)); }