想法有了，但自己写折腾了好久，还是练的太少了，贴出来，有改进的地方希望提出来，大家共同学习~~ 自顶向下： ``` public int minimumTotal(List<List<Integer>> triangle) { int level = triangle.size(); return helper(triangle, 0, 0, level); } // 参数i表示当前层，level表示共有多少层 public int helper(List<List<Integer>> triangle, int i, int j, int level) { if(i >= level || j >= triangle.get(i).size()) return 0; int left = helper(triangle, i + 1, j, level); int right = helper(triangle, i + 1, j + 1, level); return Math.min(left, right) + triangle.get(i).get(j); } ``` 带备忘录的自顶向下： ``` public static int minimumTotal(List<List<Integer>> triangle) { int level = triangle.size(); List<List<Integer>> memory = new ArrayList<>(); memory.add(new ArrayList<>()); return helper(triangle, 0, 0, level, memory); } // 参数i表示当前层，level表示共有多少层 public static int helper(List<List<Integer>> triangle, int i, int j, int level, List<List<Integer>> memory) { if(i >= level || j >= triangle.get(i).size()) return 0; // 到了最后一层，就将结果全部放入 if(i == level - 1 && memory.get(i).isEmpty()) { for(int k = 0; k < triangle.get(i).size(); k++) memory.get(i).add(triangle.get(i).get(k)); } if(!memory.get(i).isEmpty() && j < memory.get(i).size() && memory.get(i).get(j) != null) return memory.get(i).get(j); if(memory.size() < level) // 防止添加回溯的过程又添加 memory.add(new ArrayList<>()); int left = helper(triangle, i + 1, j, level, memory); int right = helper(triangle, i + 1, j + 1, level, memory); memory.get(i).add(Math.min(left,right) + triangle.get(i).get(j)); return memory.get(i).get(j); } ```

老师讲的非常好，动态倒推的3部曲 1. 定义状态 dp[i][j] : 从底部到 triangel[i][j] 的路径的最小值 2.转移方程式: dp[i][j] = triangle[i][j] + min(dp[i+1][j],dp[i+1][j+1]); 3.定义初始化的值: dp[rowMax][j] = triangle[rowMax][j] 我总感觉用二维数组存储更好理解，老师的代码里面是用 一维数组存储 最小值，感觉很N,但对于初学者 有点 看不太懂 for (int i = rowMax-1; i >=0 ; i--) { for (int j = 0; j <=colMax && triange[i][j] >0 (假设 0是初始值) ;j ++ ) { dp[i][j] = triangle[i][j] + min(dp[i+1][j],dp[i+1][j+1]); } } return dp[0][0];

留言长度限制，只有分开了，这是动态规划的 动态规划： ``` public static int minimumTotal(List<List<Integer>> triangle) { int level = triangle.size(); List<Integer> min = new ArrayList<>(triangle.get(level - 1)); for(int i = level - 2; i >= 0; i--) { int len = triangle.get(i).size(); for(int j = 0, k = 0; j < len && k < len; j++, k++) { int tmp = Math.min(min.get(k), min.get(k + 1)) + triangle.get(i).get(j); min.set(j, tmp); } min.remove(min.size() - 1); // 每次重置后，最后一个就不需要了 } return min.get(0); } ```

老师，我自己怎么是从上到下递推的，这样有问题吗？

老师讲的很好，看了两遍动态规划这个系列，动态规划突然开窍了，感觉这个算法太牛了

这些算法，都不是一遍就能看懂的，得看好几遍

动态规划可以理解自己一生的路都已知，然后从死到生再走一遍吗？

老师讲得思想方法很重要，递归--》存储--》递推 现在看到能递归的就反着想，然后找上一步能保存到下一步的数据结构，越简单的越好。

写这道题时候， 我还没学习过动态规划， 然后我从上往下写， 但明显代码没有从下往上优美。 JS版本（从上往下）： /** * @param {number[][]} triangle * @return {number} */ var minimumTotal = function(triangle) { for (let i = 1; i < triangle.length; i++) { for (let j = 0; j < triangle[i].length; j++) { const prev = triangle[i - 1]; const cur = triangle[i]; if (j === 0) triangle[i][j] += prev[0]; else if (j === cur.length - 1) triangle[i][j] += prev[prev.length - 1]; else triangle[i][j] += Math.min(prev[j - 1], prev[j]); } } return Math.min(...triangle[triangle.length - 1]); }; JS版本（从下往上）： /** * @param {number[][]} triangle * @return {number} */ var minimumTotal = function(triangle) { const mini = triangle[triangle.length - 1]; for (let i = triangle.length - 2; i >= 0; i--) { for (let j = 0; j < triangle[i].length; j++) { mini[j] = triangle[i][j] + Math.min(mini[j], mini[j + 1]); } } return mini[0]; }; 被mini数组的设定震惊到了。

递归和递推的概念终于理解的比较清楚了，感谢！