题目
    https://leetcode-cn.com/problems/triangle/comments/
    java解

    1. package com.wz;
    3. import java.util.Arrays;
    4. import java.util.List;
    6. public class Algorithm {
    7.     public static void main(String[] args) {
    8.         List<List<Integer>> triangle = Arrays.asList(
    9.                 Arrays.asList(2),
    10.                 Arrays.asList(3, 4),
    11.                 Arrays.asList(6, 5, 7),
    12.                 Arrays.asList(4, 1, 8, 3)
    13.         );
    14.         int res = new Solution().minimumTotal(triangle);
    15.         System.out.println(res);
    16.     }
    17. }
    20. class Solution {
    21.     Integer[][] memo;
    23.     public int minimumTotal(List<List<Integer>> triangle) {
    24.         memo = new Integer[triangle.size()][triangle.size()];
    25.         return dfs(triangle, 0, 0);
    26.     }
    28.     private int dfs(List<List<Integer>> triangle, int i, int j) {
    29.         if (i == triangle.size()) {
    30.             return 0;
    31.         }
    32.         if (memo[i][j] != null) {
    33.             return memo[i][j];
    34.         }
    35.         return Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
    37.     }
    38. }

    js翻译一遍，结果就是不正确，我怎么都找不到问题，辗转睡不着

    1. /**
    2.  * @param {number[][]} triangle
    3.  * @return {number}
    4.  */
    5. let memo = []
    6. var minimumTotal = function (triangle) {
    7.     memo = new Array(triangle.length).fill(new Array(triangle.length).fill(null))
    8.     return dfs(triangle, 0, 0)
    9. };
    11. function dfs(triangle, i, j) {
    12.     if (i === triangle.length)
    13.         return 0
    14.     if (memo[i][j] !== null)
    15.         return memo[i][j]
    16.     return memo[i][j] = triangle[i][j] + Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1))
    18. }
    19. minimumTotal([[2],[3,4],[6,5,7],[4,1,8,3]])

    最后发现是new Array().fill()的问题，我本想快速的初始化一个二维数组
    image.png
    这里的第一个fill是用一个对象填充的，对这个对象进行修改会造成连锁反应。

    百度了一下，网上已经有同样爬坑的了
    image.png
    这是我的新答案

    1. /**
    2.  * @param {number[][]} triangle
    3.  * @return {number}
    4.  */
    5. let m = []
    6. var minimumTotal = function(triangle) {
    7.     for(let i = 0; i < triangle.length; i++){
    8.         const arr = new Array(triangle.length).fill(null)
    9.         m.push(arr)
    10.     }
    11.     return dfs(triangle, 0, 0)
    12. };
    14. function dfs(triangle, i, j){
    15.     if(i === triangle.length)
    16.         return 0
    17.     if(m[i][j] !== null)
    18.         return m[i][j]
    19.     return m[i][j] = triangle[i][j] + Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1))
    20. }

    提交失败但是测试能通过，我无语了已经
    image.png
    image.png