动态规划

1. 基本思想

分治算法
分治算法的基本思想是将一个规模较大的问题分解为若干个规模较小的子问题，这些子问题相互独立^[1]且与原问题性质相同。求出子问题的解，就可得到原问题的解。

动态规划
动态规划算法的基本思想和分治算法一样，不过动态规划算法通常用于求解具有某种最优性质^[2]的问题，并且经分解得到子问题往往不是互相独立的。

动态规划如何解决分治算法问题：
问题1：分解得到的子问题数目太多，并且有些子问题被重复计算了很多次。
解决方法：用一个表(数组)来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中这样就可以避免大量的重复计算
问题2：子问题之间的依赖
解决方法：通过递推公式计算子问题的依赖关系。找到子问题依赖之间的关系(一般是第n项解和前1…n-1项解之间的联系)，用数学公式表达出来。

1. 独立：后一个问题的解是否依赖前一个问题的解
2. 最优性质：在某个问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

2. 分类

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。

1. 线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
2. 区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
3. 树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
4. 背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶等

3. 实战

1. 先来一个简单的爬楼梯
   图解
   得到递推公式 dp[n] = dp[n-1] + dp[n-2];

    public int climbStairs(int n) {
        int[] nums = new int[n + 1];
        nums[0] = 1;
        nums[1] = 1;
        for (int i = 2, length = nums.length; i < length; i++) {
            nums[i] = nums[i - 1] + nums[i - 2];
        }
        return nums[n];
    }

同理：那么如果要是一次能跳1，2，3个台阶呢？
递推公式：dp[n] = dp[n-1] + dp[n-2] + dp[n-3];

2. 打家劫舍
   图解
   递推公式：dp[i] = max(dp[i-2]+nums[i] , dp[i-1])

    public static int rob2(int[] nums) {
        if(nums.length==0) return 0;
        if(nums.length==1) return nums[0];
        if(nums.length==2) return Math.max(nums[0],nums[1]);

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);

        for(int i=2;i<nums.length;i++){
            dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[nums.length-1];
    }