java - Java leetcode 问题 Array Vs ArrayList 120.triangle

Question

我试图解决问题 120.triangle，它是以下内容：

给定一个三角形，找到从上到下的最小路径和。每一步你都可以移动到下一行的相邻数字。

以下是我的解决方案：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {

       List<Integer> latestSum = new ArrayList<>();

        for(int i = 0;i <= triangle.size()+2;i++){
            latestSum.add(i,Integer.MAX_VALUE);

        }

      return  helper (triangle, 0,0,latestSum);     
    }

    int helper(List<List<Integer>> triangle, int level, int index, List<Integer> cache){

        if(level == triangle.size()-1){

         return  triangle.get(level).get(index);  
        }

        int firstOpreand = cache.get(level+1);

        if(firstOpreand == Integer.MAX_VALUE){

            firstOpreand = helper(triangle, level+1,index, cache);
        }
         int secondOpreand = helper(triangle, level+1,index+1, cache);

         cache.add(level+1, secondOpreand);
       return triangle.get(level).get(index)+Math.min(firstOpreand,secondOpreand)  ; 

    }
}

由于某种原因，这个解决方案没有通过所有测试用例并给出错误，然后我在讨论部分找到了另一个通过所有测试用例的解决方案，就是这样

class Solution {
    public int minimumTotal(List<List<Integer>> tri) {
     if (tri.size() == 0) {
        return 0;
    }
    if (tri.size() == 1) {
        return tri.get(0).get(0);
    }
    Integer[] dp = new Integer[tri.size()];
    return min(tri, 0, 0, dp);


    }



public int min(List<List<Integer>> tri, int row, int currIndex, Integer[] dp) {
    if (row == tri.size() - 1) {
        return tri.get(row).get(currIndex);
    }
    int minLeft;
    if (dp[row + 1] != null) {
        minLeft = dp[row + 1];
    } else {
        minLeft = min(tri, row + 1, currIndex, dp);   
    }
    int minRight = min(tri, row + 1, currIndex + 1, dp);

    dp[row + 1] = minRight;

    return tri.get(row).get(currIndex) + Math.min(minLeft, minRight);
}
}

也许我错过了一些东西，所以我想我可以换一只眼睛，我看到两种解决方案几乎相同，但第一个不起作用，这是失败的用例之一

[[-7],[-2,1],[-5,-5,9],[-4,-5,4,4],[-6,-6,2,-1,-5] ,[3,7,8,-3,7,-9],[-9,-1,-9,6,9,0,7],[-7,0,-6,-8,7, 1,-4,9],[-3,2,-6,-9,-7,-6,-9,4,0],[-8,-6,-3,-9,-2, -6,7,-5,0,7],[-9,-1,-2,4,-2,4,4,-1,2,-5,5],[1,1,-6 ,1,-2,-4,4,-2,6,-6,0,6],[-3,-3,-6,-2,-6,-2,7,-9,-5 ,-7,-5,5,1]]

正确的解决方案是 -63 但第一个是给 -153

标签： javaarraysperformancerecursionarraylist