从下面往上 可以建立一个cache 这个点往下search过已经知道最小值了 下一次访问的时候就可以直接取值， 因为一般一个点都会被上面访问两次，如果不这样就会time limit错误
1 class Solution { 2 public int minimumTotal(List<List<Integer>> triangle) { 3 if(triangle == null) return 0; 4 Integer[][] cache = new Integer[triangle.size()][triangle.size()]; 5 return backtrack(triangle, 0, 0, cache); 6 7 } 8 9 public int backtrack(List<List<Integer>> triangle, int level, int index, Integer[][] cache) { 10 if(level+1 >= triangle.size()) { 11 return triangle.get(level).get(index); 12 } 13 if( cache[level][index] != null) return cache[level][index]; 14 return cache[level][index] = triangle.get(level).get(index) + Math.min(backtrack(triangle, level+1, index, cache), backtrack(triangle, level+1, index+1, cache)); 15 16 17 18 } 19 }
原文：https://www.cnblogs.com/goPanama/p/9691633.html