資料結構與演演算法 | 動態規劃演演算法（Dynamic Programming）

上一篇文末已經提到了記憶化搜尋是動態規劃（Dynamic Programming）的一種形式，是一種自頂向下（Top-Down）的思考方式，通常採用遞迴的編碼形式；既然動態規劃有自頂向下（Top-Down）的遞迴形式，自然想到對應的另外一種思考方式自底向上（ Bottom-Up ），也就是本篇要寫的內容。

什麼是自底向上的思考？不空談理論，還是借個實際題目來體會。

自底向上（ Bottom-Up ）

LeetCode 53. 最大子陣列和【中等】

給你一個整數陣列nums請你找出一個具有最大和的連續子陣列（子陣列最少包含一個元素），返回其最大和。子陣列是陣列中的一個連續部分。

範例：

輸入：nums = -2,1,-3,4,-1,2,1,-5,4
輸出：6
解釋：連續子陣列 4,-1,2,1 的和最大為 6 。

對於連續子陣列求和，先 想象 一些簡單場景

場景一：陣列只有1個元素，那麼最大和就1種情況也就是 第1個元素；
場景二：陣列擴充套件到2個元素，那麼最大和就有3種情況了：第1個元素、第1個元素+第2個元素、第2個元素。

對比場景一與場景二，由於第2個元素的出現從而導致最大和子陣列可能包含第2個元素，從而新出現了：第1個元素+第2個元素、第2個元素兩種情況，多出來的其實是：第2個元素作為子陣列尾元素 的情況。

分析下 以第2個元素作為子陣列尾元素的最大和？ 第2個元素 + 某個數 要最大，自然這裡的 某個數 越大越好，因此它的一個選擇就是 第2個元素 + 前一個元素(第1個元素)作為子陣列尾元素的最大和 ；但考慮到 某個數 可能為負數，所以最大和還有一種選擇就是 第2個元素 了。

綜上分析，以第2個元素作為子陣列尾元素的最大和就是在：以第1個元素作為陣列尾元素最大和 + 第2個元素，第2個元素 中選一個較大的。

如果再加入第3個元素，以第3個元素作為子陣列尾元素的最大和選擇同理也是：第3個元素，第3個元素+以第2個元素作為子陣列尾元素的最大和中選一個較大的。

依次類推第n個元素 a[n] 作為子陣列尾元素的最大和 s[n]，用公式來說就是：

 s[n] = Max( a[n] , s[n-1] + a[n] )

所謂整個陣列的最大和的連續子陣列，無非是在第1、第2...第n個元素結尾的最大和中選取最大的,這樣也就完成題目的解答了。分析清楚了，程式碼實現上就比較簡單了：

public int maxSubArray(int[] nums) {
        
        int state = nums[0],max = state;
        for(int i = 1; i < nums.length; i++){

        	// s[n] = Max(a[n], s[n-1] + a[n])
            state = Math.max(nums[i],state + nums[i]);
            max = Math.max( max , state );
        }
        return max;

    }

可以看到解題的整個過程，從最簡單基本的情況開始，一步一步推導到結果。這就是自底向上（ Bottom-Up ）的推導過程，實現上通常使用的是遞推的編碼方式。

階段（Stage）、狀態（State）、決策（Decision）

如果把推導第1個元素、第2個元素...第n個元素結尾子陣列最大和看成一個個決策階段，s[n]可以看作第n個階段決策後的狀態，所謂上題的決策就是指取最大值。這裡值得注意點的是，第n個階段決策只依賴於第n-1個階段的狀態。

以上就是動態規劃中的三個重要概念：階段、狀態、決策。

階段（Stage）：階段表示解決問題的不同時間點或步驟。問題通常可以劃分為多個階段，每個階段都對應於解決問題的一個關鍵步驟。動態規劃演演算法通過逐個處理這些階段來解決問題。
狀態（State）：狀態是描述問題區域性情況的變數。在每個階段，問題的狀態會發生變化。動態規劃演演算法的目標是定義狀態，使得問題的解可以通過不同階段的狀態之間的轉移關係來表示。狀態是問題的關鍵抽象，對於不同的問題，狀態的選擇可能會有很大的差異。
決策（Decision）：決策是在每個階段基於當前狀態做出的選擇。這些決策會影響問題的狀態轉移，從而影響問題的最終解。動態規劃演演算法的關鍵之一是找到在每個階段應該做出的最優決策，以達到整體問題的最優解。

對於遞推公式： s[n] = Max(a[n], s[n-1] + a[n])，動態規劃中也被稱作 狀態轉移方程。

一般性解題步驟（General Problem-solving Steps）

如果非常細緻的朋友會注意到，上述解題過程中最初用了 「想象」 一詞；行文如此是為了更好的描述自底向上的過程。如果是解答一道從來沒接觸過的動態規劃類演演算法題，通過「想象」推導分析出階段來難度可能過高，當然不排除想象力豐富的朋友有此能力。

前文提到的階段也好、決策也好都圍繞的是狀態；定義動態規劃的狀態是關鍵，可以說找到狀態轉移方程問題就已經解決了60%。這裡給出一些一般性的解題步驟_參考_，以降低 「想象」的難度。

定義狀態：確定問題的狀態，即描述問題區域性情況的變數。狀態的選擇對問題的建模至關重要，不同的狀態選擇可能導致完全不同的動態規劃解法。
找到狀態轉移方程：對於每個狀態，找到它與其他狀態之間的關係，即狀態轉移方程。狀態轉移方程描述了問題從一個階段到下一個階段的轉移規則，是動態規劃問題的核心。
初始化：定義問題的初始狀態並進行初始化。
確定邊界條件：確定問題的邊界條件，即在最小規模下直接解決問題的情況。這是遞迴或遞推開始的基礎，通常是問題的最小子問題。
計算順序：確定計算狀態的順序，也是劃分階段。可以採用自頂向下（Top-Down）的遞迴方法，也可以採用自底向上（Bottom-Up）的遞推方法。
計算最終解：根據 1-5 的分析結果進行編碼，最終解通常是在問題的最後一個階段計算得到的，它可能儲存在動態規劃表格的特定位置。

一些場景下可能需要記錄路徑或決策,如果需要記錄最優解的具體路徑或決策，可以在計算的過程中進行記錄.當然，以上也只是建議的步驟並非一定要如此。

PS: 這裡不妨多說一點狀態，在上一篇中有提到過動態規劃是最靈活的演演算法之一；靈活的原因就是面對不同問題狀態設計的多樣性；如果要想快速解出動態規劃類題，還是需要多多練習，積累一些設計狀態的經驗。因此初學時不用太在意對比經驗豐富的朋友，解決動態規劃類效率較慢，差距可能只在於缺少各種狀態設計的經驗積累。

基本應用範例（Basic Examples）

LeetCode 122. 買賣股票的最佳時機 II【中等】

給你一個整數陣列 prices ，其中 pricesi 表示某支股票第 i 天的價格。
在每一天，你可以決定是否購買和/或出售股票。你在任何時候最多只能持有一股股票。你也可以先購買，然後在同一天出售。返回你能獲得的最大利潤。

範例：

輸入：prices = 1,2,3,4,5
輸出：4
解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 。總利潤為 4 。

狀態定義，preSell 定義為上一天沒有持股情況下最大利潤，preBuy 定位為持有股票情況下最大利潤。
狀態轉移方程：

	currentSell = Max( preBuy + prices[i], preSell)
	currentBuy = Max( preSell - prices[i], preBuy)

計算下一個狀態時，current 也就變成了 pre。考慮到最終最大利潤一定時不持股情況，因此 max 只需記錄過程中 currentSell 的最大值。

初始化以及邊界條件，不持股下 preSell 為 0，持股下買入了第一隻股票 preBuy 為 -prices[0]

public int maxProfit(int[] prices) {

        int preSell = 0,preBuy = -prices[0];
        int max = 0;
        for(int i = 1; i < prices.length; i++){
            
            int currentSell = Math.max(preSell,preBuy + prices[i]);
            int currentBuy = Math.max(preBuy, preSell - prices[i]);

            preSell = currentSell;
            preBuy = currentBuy;

            max = Math.max(currentSell,max);
        }
        return max;
    }

LeetCode 198. 打家劫舍【中等】

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數陣列，計算你不觸動警報裝置的情況下，一夜之內能夠偷竊到的最高金額。

範例:

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然後偷竊 3 號房屋 (金額 = 3)。偷竊到的最高金額 = 1 + 3 = 4 。

這裡可以體會下設計狀態的經驗，相信有前一題的鋪墊，對於這道題的狀態設計就比較類似了。

定義狀態，preSteal 前一夜偷了的最高金額，preNosteal 前一夜沒偷的最高金額
狀態轉移方程：

	nosteal = Max( preNosteal , preSteal )
	steal = preNosteal + nums[i]

初始化以及邊界條件，略

	public int rob(int[] nums) {

        int preSteal = nums[0],preNosteal = 0;

        for(int i = 1; i < nums.length; i++){

            int nosteal = Math.max(preNosteal,preSteal);
            int steal = preNosteal + nums[i];

            preSteal = steal;
            preNosteal = nosteal;
        }

        return Math.max(preNosteal,preSteal);
    }

LeetCode 377. 組合總和 Ⅳ【中等】

給你一個由不同整陣列成的陣列 nums ，和一個目標整數 target 。請你從 nums 中找出並返回總和為 target 的元素組合的個數。
題目資料保證答案符合 32 位整數範圍。

範例:

輸入：nums = 1,2,3, target = 4
輸出：7
解釋：所有可能的組合為：(1, 1, 1, 1)、(1, 1, 2)、(1, 2, 1)、(1, 3)、(2, 1, 1)、(2, 2)、(3, 1)。請注意，順序不同的序列被視作不同的組合。

這個類似於01揹包的問題，狀態設計上也比較類似

定義狀態，s[i] 代表目標整數 i 時，組合的個數
狀態轉移方程：

對於整數 nums[j] , 如果 i >= nums[j] 代表有可能被 nums[j] 組成
相當於 s[ i-nums[j] ] 組合裡面 都加上個 nums[j]元素 ，
所以s[i] 組合數新增了 s[ i-nums[j] ] 個。

s[i] += s[ i-nums[j] ]

初始化狀態：s[0] 代表著不選取任何元素的是 target = 0，此時不選取任何元素為唯一的方案。

public int combinationSum4(int[] nums, int target) {

        int[] s = new int[target+1];
        s[0] = 1;

        for(int i = 1; i <= target; i++){

            for(int j = 0; j < nums.length; j++){
                if(i - nums[j] < 0) continue;
                s[i] += s[i - nums[j]] ;
            }
        }
        return s[target];
    }

歡迎關注 Java研究者專欄、部落格、公眾號等