数据结构与算法 | 动态规划算法（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個元素；undefined對比場景一 與 場景二，由于第2個元素的出現 從而導致最大和子數組 可能包含第2個元素，從而新出現了：第1個元素+第2個元素、第2個元素兩種情況，多出來的其實是：第2個元素作為子數組尾元素的情況。 - 場景二 ：數組擴展到2個元素，那么最大和就有3種情況了：
第1個元素、第1個元素+第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研究者專欄、博客、公眾號等
總結
以上是生活随笔為你收集整理的数据结构与算法 | 动态规划算法（Dynamic Programming）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： clickHouse-golang
- 下一篇： Linux下redis的安装下载以及连接