演算法(01)--動態規劃詳解

求解動態規劃的核?問題是窮舉，因為要求最值，肯定要把所有可?的答案窮舉出來，然后在其中找最值唄，

?先，動態規劃的窮舉有點特別，因為這類問題存在「重疊?問題」，如果 暴?窮舉的話效率會極其低下，所以需要「備忘錄」或者「DP table」來優 化窮舉程序，避免不必要的計算， ?且，動態規劃問題?定會具備「最優?結構」，才能通過?問題的最值得到原問題的最值，

另外，雖然動態規劃的核?思想就是窮舉求最值，但是問題可以千變萬化， 窮舉所有可?解其實并不是?件容易的事，只有列出正確的「狀態轉移?程」才能正確地窮舉，

在實際的演算法問題中，寫出狀態轉移?程是最困難的，這也就是為什么很多朋友覺得動態規劃問題困難的原因，我 來提供我研究出來的?個思維框架，輔助你思考狀態轉移?程：

明確「狀態」 -> 定義 dp 陣列/函式的含義 -> 明確「選擇」-> 明確 base case，

《斐波那契數列》— 主要是讓你明?什么是重疊?問題

1.1) 暴?遞回

斐波那契數列的數學形式就是遞回的，寫成代碼就是這樣：

    int	fib(int	N){
    if(N ==	1 || N	==	2) return 1;
    return	fib(N-1) + fib(N-2);
}

PS：但凡遇到需要遞回的問題，最好都畫出遞回樹，這對你分析演算法的復雜度，尋找演算法低效的原因都有巨?幫助，

想要計算原問題f(20)，我就得先計算出?問題f(19)和f(18)，然后要計算f(19)，我就要先算出?問題f(18)和 f(17)，以此類推，最后遇到f(1)或者f(2)的時候，結果已知，就能直接回傳結果，遞回樹不再向下??了，

遞回演算法的時間復雜度怎么計算？?問題個數乘以解決?個?問題需要的時間，

?問題個數，即遞回樹中節點的總數,顯然?叉樹節點總數為指數級別，所以?問題個數為O(2^n)，
解決?個?問題的時間，在本演算法中，沒有回圈，只有f(n-1)+f(n-2)? 個加法操作，時間為O(1)， 所以，這個演算法的時間復雜度為O(2^n)，指數級別，爆炸，

觀察遞回樹，很明顯發現了演算法低效的原因：存在?量重復計算，?如f(18)被計算了兩次，?且你可以看到，以f(18)為根的這個遞回樹體量巨?，多算?遍，會耗費巨?的時間，更何況，還不?f(18)這?個節點 被重復計算，所以這個演算法及其低效，
這就是動態規劃問題的第?個性質：重疊?問題，下?我們想辦法解決這個問題，

1.2) 帶備忘錄的遞回解法

明確了問題，其實就已經把問題解決了?半，即然耗時的原因是重復計算， 那么我們可以造?個「備忘錄」，每次算出某個?問題的答案后別急著返 回，先記到「備忘錄」?再回傳；每次遇到?個?問題先去「備忘錄」?查 ?查，如果發現之前已經解決過這個問題了，直接把答案拿出來?，不要再耗時去計算了，
?般使??個陣列充當這個「備忘錄」，當然你也可以使?哈希表（字 典），思想都是?樣的，

    int fib(int N) {
        if (N < 1) return 0;
        //	備忘錄全初始化為0
        vector<int> memo (N + 1, 0);
        //	初始化最簡情況
        return helper(memo, N);
    }

    int helper(vector<int>& memo, int n) {
        //	base	case
        if (n == 1 || n == 2) return 1;
        //	已經計算過
        if (memo[n] != 0) return memo[n];
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        return memo[n];
    }

現在，畫出遞回樹，你就知道「備忘錄」到底做了什么:

實際上，帶「備忘錄」的遞回演算法，把?棵存在巨量冗余的遞回樹通過「剪 枝」，改造成了?幅不存在冗余的遞回圖，極?減少了?問題（即遞回圖中 節點）的個數，

遞回演算法的時間復雜度怎么算？----- ?問題個數乘以解決?個?問題需要的時間，

?問題個數，即圖中節點的總數，由于本演算法不存在冗余計算，?問題就是 f(1) , f(2) , f(3) … f(20) ，數量和輸?規模 n = 20 成正?，所以?問題個數為 O(n)， 解決?個?問題的時間，同上，沒有什么回圈，時間為 O(1)， 所以，本演算法的時間復雜度是 O(n)，?起暴?演算法，是降維打擊，
?此，帶備忘錄的遞回解法的效率已經和迭代的動態規劃解法?樣了，實際 上，這種解法和迭代的動態規劃已經差不多了，只不過這種?法叫做「?頂向下」，動態規劃叫做「?底向上」，
啥叫「?頂向下」？注意我們剛才畫的遞回樹（或者說圖），是從上向下延 伸，都是從?個規模較?的原問題?如說 f(20) ，向下逐漸分解規模，直 到 f(1) 和 f(2) 觸底，然后逐層回傳答案，這就叫「?頂向下」， 啥叫「?底向上」？反過來，我們直接從最底下，最簡單，問題規模最?的 f(1) 和 f(2) 開始往上推，直到推到我們想要的答案 f(20)，這就是動態規劃的思路，這也是為什么動態規劃?般都脫離了遞回，?是由回圈迭代完成計算，

1.3) dp 陣列的迭代解法

有了上?步「備忘錄」的啟發，我們可以把這個「備忘錄」獨?出來成為? 張表，就叫做 DP table吧，在這張表上完成「?底向上」的推算豈不美哉！

    int fib(int N) {
        vector<int> dp (N + 1, 0);
        //	base	case
        dp[1] = dp[2] = 1;
        for (int i = 3; i <= N; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[N];
    }

畫個圖就很好理解了，?且你發現這個 DP table 特別像之前那個「剪枝」后 的結果，只是反過來算?已，實際上，帶備忘錄的遞回解法中的「備忘錄」，最終完成后就是這個DP table，所以說這兩種解法其實是差不多的， ?部分情況下效率也基本相同， 這?引出「狀態轉移?程」這個名詞，實際上就是描述問題結構的數學形式：

為啥叫「狀態轉移?程」？為了聽起來?端，你把 f(n) 想做?個狀態n，這 個狀態n是由狀態 n - 1 和狀態 n - 2 相加轉移?來，這就叫狀態轉移，僅此?已， 你會發現，上?的?種解法中的所有操作，例如 return f(n-1) + f(n- 2)， dp[i] = dp[i - 1] + dp[i - 2]，以及對備忘錄或DP table的初始化操作，都是圍繞這個?程式的不同表現形式，可?列出「狀態轉移?程」的重要性，它是解決問題的核?，很容易發現，其實狀態轉移?程直接代表著暴?解法，

千萬不要看不起暴?解，動態規劃問題最困難的就是寫出狀態轉移?程，即 這個暴?解，優化?法??是?備忘錄或者 DP table，再?奧妙可?， 這個例?的最后，講?個細節優化，細?的讀者會發現，根據斐波那契數列 的狀態轉移?程，當前狀態只和之前的兩個狀態有關，其實并不需要那么? 的?個DP table來存盤所有的狀態，只要想辦法存盤之前的兩個狀態就? 了，所以可以進?步優化，把空間復雜度降為O(1)：

    int fib(int n) {
        if (n == 2 || n == 1) return 1;
        int prev = 1, curr = 1;
        for (int i = 3; i <= n; i++) {
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    } 

《湊零錢問題 》— 主要是讓你明?什么是最優?結構

先看下題?：給你 k 種?值的硬幣，?值分別為 c1, c2 … ck ，每種硬 幣的數量?限，再給?個總?額 amount ，問你最少需要?枚硬幣湊出這個 ?額，如果不可能湊出，演算法回傳 -1 ，演算法的函式簽名如下：

//	coins中是可選硬幣?值，amount是?標?額 
	int	coinChange(int[] coins,	int	amount);

?如說 k = 3 ，?值分別為 1，2，5，總?額 amount = 11，那么最少需 要 3 枚硬幣湊出，即 11 = 5 + 5 + 1， 你認為計算機應該如何解決這個問題？顯然，就是把所有肯能的湊硬幣?法 都窮舉出來，然后找找看最少需要多少枚硬幣，

2.1) 暴?遞回

?先，這個問題是動態規劃問題，因為它具有「最優?結構」的，要符合 「最優?結構」，?問題間必須互相獨?，啥叫相互獨?？你肯定不想看數學證明，我??個直觀的例?來講解，
?如說，你的原問題是考出最?的總成績，那么你的?問題就是要把語?考 到最?，數學考到最?…… 為了每門課考到最?，你要把每門課相應的選擇題分數拿到最?，填空題分數拿到最?…… 當然，最終就是你每門課都是滿分，這就是最?的總成績， 得到了正確的結果：最?的總成績就是總分，因為這個程序符合最優?結 構，“每門科?考到最?”這些?問題是互相獨?，互不?擾的，
但是，如果加?個條件：你的語?成績和數學成績會互相制約，此消彼?， 這樣的話，顯然你能考到的最?總成績就達不到總分了，按剛才那個思路就會得到錯誤的結果，因為?問題并不獨?，語?數學成績?法同時最優，所 以最優?結構被破壞，
回到湊零錢問題，為什么說它符合最優?結構呢？?如你想求 amount = 11 時的最少硬幣數（原問題），如果你知道湊出 amount = 10 的最少硬幣 數（?問題），你只需要把?問題的答案加?（再選?枚?值為1 的硬幣） 就是原問題的答案，因為硬幣的數量是沒有限制的，?問題之間沒有相互制約，是互相獨?的， 那么，既然知道了這是個動態規劃問題，就要思考如何列出正確的狀態轉移?程？

• 先確定「狀態」，也就是原問題和?問題中變化的變數，由于硬幣數量? 限，所以唯?的狀態就是?標?額 amount；
• 然后確定 dp 函式的定義：當前的?標?額是 n，?少需要dp(n)個硬 幣湊出該?額；
• 然后確定「選擇」并擇優，也就是對于每個狀態，可以做出什么選擇改變當前狀態，具體到這個問題，?論當的?標?額是多少，選擇就是從?額串列coins中選擇?個硬幣，然后?標?額就會減少：

    //	偽碼框架
    def coinChange(coins:List[int], amount:int):
        //	定義：要湊出?額 n，?少要dp(n)個硬幣
        def dp(n):
        //	做選擇，選擇需要硬幣最少的那個結果
        for coin in coins:
        res=min(res,1+dp(n-coin))
        return res
        //	我們要求的問題是 dp(amount)
        return dp(amount)

• 最后明確 basecase，顯然?標?額為 0 時，所需硬幣數量為0；當?標?額?于 0 時，?解，回傳-1：

    def coinChange(coins:List[int], amount:int):
        def dp(n):
        // base case 
        if n==0:return 0
        if n< 0:return-1
        // 求最?值，所以初始化為正?窮								
        res=float('INF')
        for coin in coins:
        subproblem=dp(n-coin)
        // ?問題?解，跳過												
        if subproblem==-1:continue
        res=min(res,1+subproblem)
        return res if res!=float('INF')else-1
        return dp(amount)

?此，狀態轉移?程其實已經完成了，以上演算法已經是暴?解法了，以上代碼的數學形式就是狀態轉移?程：

?此，這個問題其實就解決了，只不過需要消除?下重疊?問題，?如amount = 11, coins = {1,2,5} 時畫出遞回樹看看：

時間復雜度分析：?問題總數 x 每個?問題的時間，
?問題總數為遞回樹節點個數，這個?較難看出來，是 O(n^k)，總之是指數級別的，每個?問題中含有?個 for 回圈，復雜度為 O(k)，所以總時間復 雜度為O(k * n^k)，指數級別，

2.2) 帶備忘錄的遞回

只需要稍加修改，就可以通過備忘錄消除?問題：

        def coinChange(coins:List[int],amount:int):
        //	備忘錄
        memo=dict()
        def dp(n):
            //	查備忘錄，避免重復計算
            if n in memo:return memo[n]
            if n==0:return 0
            if n<	0:return-1
            res=float('INF')
            for coin in coins:
                subproblem=dp(n-coin)
                if subproblem==-1:continue
                res=min(res,1+subproblem)

            //	記?備忘錄
            memo[n]=res if res!=float('INF') else-1
            return memo[n]
        return dp(amount)

很顯然「備忘錄」??減?了?問題數?，完全消除了?問題的冗余，所以?問題總數不會超過?額數n，即?問題數?為 O(n)，處理?個?問題的時間不變，仍是O(k)，所以總的時間復雜度是O(kn)，

2.3) dp 陣列的迭代解法

當然，我們也可以?底向上使? dp table 來消除重疊?問題， dp陣列的定義和剛才dp函式類似，定義也是?樣的： dp[i] = x 表?，當?標?額為i時，?少需要 x 枚硬幣

        int	coinChange(vector<int>&	coins,	int	amount)	{
                    //	陣列??為	amount	+	1，初始值也為	amount	+	1
       	    vector<int>	dp(amount	+	1,	amount	+	1);
       	    //	base	case
        	dp[0]=0;
        	for	(int i = 0;	i < dp.size();	i++){
        	    //	內層	for	在求所有?問題	+	1	的最?值
                for	(int coin :	coins)	{
                    //	?問題?解，跳過
                	if	(i - coin <	0)	continue;
                	dp[i] =	min(dp[i],	1 +	dp[i - coin]);
                 }
        	}
        	return	(dp[amount]	==	amount	+	1)	?	-1	:	dp[amount];
    }

PS：為啥 dp陣列初始化為 amount+ 1 呢？
因為湊成 amount?額的硬幣數最多只可能等于amount（全?1元?值的硬幣），所以初始化為amount+1就相當于初始化為正?窮，便于后續取最?值，

總結

第?個斐波那契數列的問題，解釋了如何通過「備忘錄」或者「dp table」 的?法來優化遞回樹，并且明確了這兩種?法本質上是?樣的，只是?頂向 下和?底向上的不同?已，
第?個湊零錢的問題，展?了如何流程化確定「狀態轉移?程」，只要通過狀態轉移?程寫出暴?遞回解，剩下的也就是優化遞回樹，消除重疊?問題?已，
計算機解決問題其實沒有任何奇技淫巧，它唯?的解決辦法就是窮舉，窮舉所有可能性，演算法設計??就是先思考“如何窮舉”，然后再追求“如何聰明 地窮舉”， 列出動態轉移?程，就是在解決“如何窮舉”的問題，之所以說它難，?是因為很多窮舉需要遞回實作，?是因為有的問題本?的解空間復雜，不那么容易窮舉完整， 備忘錄、DP table 就是在追求“如何聰明地窮舉”，?空間換時間的思路，是降低時間復雜度的不?法門，

本文內容來源----公眾號：labuladong 《labuladong的演算法小抄》 提取碼：g9l2