1. 基本思想

分治算法
分治算法的基本思想是將一個規(guī)模較大的問題分解為若干個規(guī)模較小的子問題，這些子問題相互獨立^[1]且與原問題性質相同。求出子問題的解，就可得到原問題的解。

動態(tài)規(guī)劃
動態(tài)規(guī)劃算法的基本思想和分治算法一樣，不過動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質^[2]的問題，并且經(jīng)分解得到子問題往往不是互相獨立的。

動態(tài)規(guī)劃如何解決分治算法問題：
問題1：分解得到的子問題數(shù)目太多，并且有些子問題被重復計算了很多次。
解決方法：用一個表(數(shù)組)來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結果填入表中這樣就可以避免大量的重復計算
問題2：子問題之間的依賴
解決方法：通過遞推公式計算子問題的依賴關系。找到子問題依賴之間的關系(一般是第n項解和前1…n-1項解之間的聯(lián)系)，用數(shù)學公式表達出來。

1. 獨立：后一個問題的解是否依賴前一個問題的解
2. 最優(yōu)性質：在某個問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優(yōu)值的解。

2. 分類

動態(tài)規(guī)劃一般可分為線性動規(guī)，區(qū)域動規(guī)，樹形動規(guī)，背包動規(guī)四類。

1. 線性動規(guī)：攔截導彈，合唱隊形，挖地雷，建學校，劍客決斗等；
2. 區(qū)域動規(guī)：石子合并， 加分二叉樹，統(tǒng)計單詞個數(shù)，炮兵布陣等；
3. 樹形動規(guī)：貪吃的九頭龍，二分查找樹，聚會的歡樂，數(shù)字三角形等；
4. 背包問題：01背包問題，完全背包問題，分組背包問題，二維背包，裝箱問題，擠牛奶等

3. 實戰(zhàn)

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];
    }