算法入门第12天

dp

120. 三角形最小路径和

这个用了巧妙的自下而上的算法，我开始使用贪心，发现不对。。

/**
 120. 三角形最小路径和
 给定一个三角形 triangle ，找出自顶向下的最小路径和。

 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。



 示例 1：

 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 输出：11
 解释：如下面简图所示：
 2
 3 4
 6 5 7
 4 1 8 3
 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 示例 2：

 输入：triangle = [[-10]]
 输出：-10


 提示：

 1 <= triangle.length <= 200
 triangle[0].length == 1
 triangle[i].length == triangle[i - 1].length + 1
 -10^4 <= triangle[i][j] <= 10^4


 进阶：

 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

 * @author zeroheart
 *
 */
public class Question120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 通过用例发现，不能使用贪心
        // int m = triangle.size();
        // int rs = triangle.get(0).get(0);;
        // int lastIndex = 0;
        // for(int i = 1; i<m; i++){
        //     List<Integer> nums = triangle.get(i);
        //     int len = nums.size();
        //     int min = Math.min(nums.get(lastIndex), nums.get(lastIndex+1));
        //     rs += min;
        //     if(nums.get(lastIndex) > nums.get(lastIndex+1))
        //         lastIndex = lastIndex+1;
        // }
        // return rs;


        // 自下而上的算法。。。很巧妙
        int size = triangle.size();
        int[][] dp = new int[size+1][size+1];

        for(int i = size-1; i>=0; i--){
            int len = triangle.get(i).size();
            for(int j=0; j<len; j++){
                dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
    }
}