剑指offer100：三角形中最小路径之和

题目：
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 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）。
示例二：
输入：triangle = [[-10]]
输出：-10
分析：
确定状态转移方程，可以用f(i,j)表示从三角形的顶部出发到达行号和列号分别为i和j（路径数字之和的最小值），同时T[i][j]表示三角形行号和列号分别为i和j的数字。如果三角形中包含n行数字，那么f(n-1,j)的最小值就是整个问题的最优解。

• 如果j等于0，也就是到达某行的第一个数字，由于路径的每一步都前往正下方或右下方的数字，而此时当前位置的左上方没有数字，那么前一步一定是来自它的正上方的数字，因此f(i,0)等于f(i-1,0)与T[i][0]之和。
• 如果i等于j，也就是当前到达某行的最后一个数字，此时它的正上方没有数字，前一步只能来自它左上方的数字，因此f(i,j)等于f(i-1,j-1)与T[i][j]之和。
• 如果当前行号和列号分别为i和j的位置位于某行的中间，那么前一步即可能来自它正上方的数字，也可能来自它左上方的数字，所以f(i,j)等于f(i-1,j)与f(i-1,j-1)的最小值再加上T [i][j]。
  第一种方法创建一个n*n的二维数组dp，当实际上只用了数组的左下部分，先用一个二重循环状态转移方程注意计算f（i，j）的值并保存到dp[i][j],然后用一个for循环找出二维数组dp最后一行的最小值作为整个问题的最优解。由于二维数组dp左下部分的每个数字都需要计算一次，因此时间复杂度是O（n^2）。假设输入的triangle是用ArrayList实现的，因此每次调用get函数的时间复杂度都是O（1）。
  优化空间效率，只需要一个一维数组dp。如果能够将f(i,j),f(i-1,j)都保存到dp[j]中，那么一个一维数组就可以保存所需的数据。
  如果从按照从左往右的顺序计算，如图：
  
  计算完f(i,j)后就顶替掉dp数组第一个元素了。在计算f(i,j+1)时可能需要f(i,j-1)，但是f(i,j-1)是原来的dp数组第一个元素但已经被顶替掉了，所以不能从左往右边来，但我们可以从右往左来计算，如果按照从右往左计算，则先计算f（i，j），需要f（i-1，j-1），f（i-1，j）。接下来计算f（i，j-1），需要用到f（i-1，j-1），f（i-1，j-2）.按照从右往左顺序计算完f（i，j）之后，将f（i，j）的值保存到dp[j]中并替换f(i-1,j),并不会带来任何问题，因此f(i-1,j)的值以后不再需要了。
  代码：

import java.util.List;

public class MinimumTotal {
//
    public int minimumTotal1(List<List<Integer>> triangle) {
//        行数
        int size = triangle.size();
        int[][] dp = new int[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = triangle.get(i).get(j);
//                如果得到的第一列下标为0，说明它的上一行元素下标也是0，因为下一行下标数字一定大于等于上一行下标数字
                if (i>0 && j==0){
                    dp[i][j] +=dp[i-1][j];
                }else if (i>0 && i==j){
//                    如果得到的行列数下标都相等，它的上一行元素一定也是对角线的元素，因为它上一行下标和它相等的不存在，只能找上一行
//                    同等下标左边那一个
                    dp[i][j] +=dp[i-1][j-1];
                }else if (i>0){
                    dp[i][j] +=Math.min(dp[i-1][j-1],dp[i-1][j]);
                }
            }
        }
        int min = Integer.MAX_VALUE;
//        找出二维数组dp最后一行的最小值作为整个问题的最优解
        for (int num:dp[size-1]){
            min = Math.min(min,num);
        }
        return min;
    }
    public int minimumTotal2(List<List<Integer>> triangle){
        int[] dp = new int[triangle.size()];
        for(List<Integer> row:triangle){
            for (int j = row.size()-1; j >=0; j--) {
                if (j==0){
                    dp[j]+=row.get(j);
                }else if (j == row.size()-1){
                    dp[j] = dp[j-1] + row.get(j);
                }else {
                    dp[j] = Math.min(dp[j],dp[j-1])+row.get(j);
                }
            }
        }
        int min = Integer.MAX_VALUE;
//        找出二维数组dp最后一行的最小值作为整个问题的最优解
        for (int num:dp){
            min = Math.min(min,num);
        }
        return min;
    }
}