首页 > 其他 > 详细

120. Triangle

时间:2018-09-23 00:04:26      阅读:93      评论:0      收藏:0      [点我收藏+]

标签:pre   clas   minimum   nbsp   []   angle   col   ret   integer   

从下面往上 可以建立一个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 }

 

120. Triangle

标签:pre   clas   minimum   nbsp   []   angle   col   ret   integer   

原文:https://www.cnblogs.com/goPanama/p/9691633.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号