leetcode 120. Triangle

柔光的暖阳◎ 2023-03-12 10:58 6阅读 0赞

给一个三角形，寻找一个从顶到底的最小的路径和，只能是临近的数字的和

[
         [2],
        [3,4],
       [6,5,7],
      [4,1,8,3]
    ]
    The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

**解题思路**

动态规划

每一层都依赖于上一层

按照从上到下，从右到左的顺序，一层一层的求

开一个`int[] f = new int[triangle.size()];`这么大的空间重复利用就可以了

class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            if(triangle == null || triangle.size() == 0) return 0;
            int[] f = new int[triangle.size()];                                 
            f[0] = triangle.get(0).get(0);                                      
            for (int i = 1; i < triangle.size(); i++) {                         
                List<Integer> innerTriangle = triangle.get(i);                  
                for (int j = innerTriangle.size() - 1; j >= 0; j--) {           
                    if (j == 0) {                                               
                        f[j] = f[j] + innerTriangle.get(j);                     
                    } else if (j == innerTriangle.size() - 1) {                 
                        f[j] = f[j-1] + innerTriangle.get(j);                   
                    } else {                                                    
                        f[j] = innerTriangle.get(j) + Math.min(f[j], f[j - 1]); 
                    }                                                           
                }                                                               
            }                                                                   
            int min = f[0];                                                     
            for (int i = 1; i < f.length; i++) {                                
                if (min > f[i]) {                                               
                    min = f[i];                                                 
                }                                                               
            }                                                                   
            return min;                                                                                                                             
           
        }
    }