LeetCode120.三角形最小路径和（动态规划、递归、记忆搜索）

120. 三角形最小路径和

题目&＃xff1a;

给定一个三角形&＃xff0c;找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 &＃43; 1 的两个结点。

例如&＃xff0c;给定三角形&＃xff1a;

[[2],[3,4],[6,5,7],[4,1,8,3]
]


自顶向下的最小路径和为 11&＃xff08;即&＃xff0c;2 &＃43; 3 &＃43; 5 &＃43; 1 &＃61; 11&＃xff09;。

思路&＃xff1a;

1. 暴力法&＃xff0c;递归&＃xff0c;n层&＃xff0c;left or right&＃xff1a;2^n
2. DP
   a.重复性&＃xff08;分治&＃xff09; problem(i,j) &＃61; min(sub(i&＃43;1,j),sub(i&＃43;1,j&＃43;1)) &＃43; a[i,j]
   b.定义状态数组 f[i,j]
   c.DP方程&＃xff1a;f[i,j] &＃61; min(f[i&＃43;1,j],f[i&＃43;1,j&＃43;1]) &＃43; a[i,j]

方法一&＃xff1a;动态规划

public int minimumTotal(List<List<Integer>> triangle) {int[] A &＃61; new int[triangle.size() &＃43; 1];for (int i &＃61; triangle.size() - 1;i >&＃61; 0; i&＃43;&＃43;) {for(int j&＃61; 0;j<triangle.get(i).size();j&＃43;&＃43;){//左右的最小者&＃xff0c;加上自身A[j] &＃61; Math.min(A[j],A[j&＃43;1]) &＃43; triangle.get(i).get(j);}}return A[0];}


方法二&＃xff1a;递归 自顶向下

int row;public int minimumTotal_1(List<List<Integer>> triangle) {row &＃61; triangle.size();return helper(0,0,triangle);}private int helper(int level, int c, List<List<Integer>> triangle) {System.out.println("helper : level&＃61;" &＃43; level &＃43; "c &＃61; " &＃43; c);//递归终止条件if (level &＃61;&＃61; row - 1){return triangle.get(level).get(c);}int left &＃61; helper(level &＃43; 1, c, triangle);int right &＃61; helper(level &＃43; 1, c &＃43; 1 , triangle);return Math.min(left,right) &＃43; triangle.get(level).get(c);}


方法三&＃xff1a;自顶向下&＃xff0c;记忆化搜索

int row;Integer[][] memo;public int minimumTotal_2(List<List<Integer>> triangle) {row &＃61; triangle.size();memo &＃61; new Integer[row][row];return helper(0,0,triangle);}private int helper(int level, int c, List<List<Integer>> triangle) {if (memo[level][c] !&＃61; null){return memo[level][c];}if (level &＃61;&＃61; row - 1){return memo[level][c] &＃61; triangle.get(level).get(c);}int left &＃61; helper(level&＃43;1,c,triangle);int right &＃61; helper(level&＃43;1,c&＃43;1,triangle);return memo[level][c] &＃61; Math.min(left,right) &＃43; triangle.get(level).get(c);}


方法四&＃xff1a;自底向上 DP

public int minimumTotal_3(List<List<Integer>> triangle) {int row &＃61; triangle.size();int[] minlen &＃61; new int[row &＃43; 1];for (int level &＃61; row - 1; level>&＃61; 0; level&＃43;&＃43;) {for (int i &＃61; 0; i <&＃61; level; i&＃43;&＃43;) {minlen[i] &＃61; Math.min(minlen[i],minlen[i&＃43;1]) &＃43; triangle.get(level).get(i);}}return minlen[0];}