120. 三角形最小路径和

题目描述:

      给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

      例如,给定三角形:

      [
         [2],
         [3,4],
         [6,5,7],
         [4,1,8,3]
       ]
       自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

题解:

    此类型题使用动态规划,共有三种:

    1):从上往下看,使用一个二维数组;

    2):从上往下看,使用一个一维数组;

    3):从下往上看,使用一个一维数组,以下提供该方法的实现代码:

public class L120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] minValue = new int[triangle.size()];
        for(int index = 0;index < triangle.size();index++){
            minValue[index] = triangle.get(triangle.size()-1).get(index);
        }
        for(int index01 = triangle.size()-2;index01>=0;index01--){
            for (int index02 = 0;index02<=index01;index02++){
                minValue[index02] = Math.min(minValue[index02],minValue[index02+1]) + triangle.get(index01).get(index02);
            }
        }
        return minValue[0];

    }
}

 

 

上一篇:动态规划专题


下一篇:动态规划潜入