动态规划

将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

递归问题》重叠子问题》记忆化搜索（自顶向下的解决问题）/动态规划（自底向上的解决问题）

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
• -104 <= triangle[i][j] <= 104

进阶：

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

解法1：递归

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        //递归解法(经测试，超过一百层超时)
        return recursiveMethod(triangle,0,0,0);
    }
    public int recursiveMethod(List<List<Integer>> triangle,int i,int j ,int value){
        value = triangle.get(i).get(j)+value;
        if(i == triangle.size()-1) {
            return value;
        }
        return Math.min(recursiveMethod(triangle,i+1,j,value),recursiveMethod(triangle,i+1,j+1,value));
    }
}

解法2：递归+记忆化搜索

class Solution {
   Integer [][] memo = null;
    public int minimumTotal(List<List<Integer>> triangle) {
        memo = new Integer[triangle.size()][triangle.size()];
        return recursiveMethod(triangle,0,0,0);
    }
    public int recursiveMethod(List<List<Integer>> triangle,int i,int j ,int value){
        if(i == triangle.size()-1) {
            return value + triangle.get(i).get(j);
        }
        if(memo[i][j] != null){
            return memo[i][j];
        }
        memo[i][j] = Math.min(recursiveMethod(triangle,i+1,j,value),recursiveMethod(triangle,i+1,j+1,value))+ triangle.get(i).get(j);
        return memo[i][j];
    }
}

解法3：动态规划

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        //动态规划 方案
        int[][] dp = new int[triangle.size()][triangle.size()];
        for (int i = 0; i < dp.length; i++) {
            dp[triangle.size()-1][i] = triangle.get(triangle.size()-1).get(i);
        }
        for (int i = triangle.size()-2; i >=0 ; i--) {
            for (int j =0; j <=i ; j++) {
                dp[i][j] =Math.min(dp[i+1][j],dp[i+1][j+1])+triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

解法4：进阶：动态规划，空间复杂度O(n)

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