動態(tài)規(guī)劃算法，3000字真正幫助你入門

今天這篇文章我構(gòu)思很久，也寫了很久，全文3330字，21張圖。如果可以的話，希望文末能點贊支持下，謝謝。

本文目標(biāo)幫助朋友們認(rèn)識到動態(tài)規(guī)劃算法之美，從而引發(fā)學(xué)習(xí)它、研究它的興趣。

一?動態(tài)規(guī)劃引言

某個問題一旦找到動態(tài)規(guī)劃的解法，一般便是接近或就是最優(yōu)解法，也正因為此，無數(shù)程序員為它著迷，大廠面試也是必考。

但是，動態(tài)規(guī)劃又非常靈活，本質(zhì)上沒有套路，問題不同，動態(tài)規(guī)劃的迭代方程就不同。而有些問題，對于計算機科學(xué)家，都難以找到迭代方程。因此，對于平平常常的我們，刷算法題時想不出動態(tài)規(guī)劃的解法，也大可不必氣餒。

雖然它很難，但卻對訓(xùn)練我們的算法思維，很有幫助！并且持續(xù)的練習(xí)、總結(jié)，也會為我們?nèi)蘸笞龀绦騼?yōu)化、性能提升、算法優(yōu)化相關(guān)工作，打下最為堅實的基礎(chǔ)。

一成不變、日復(fù)一日的重復(fù)，難免讓人感到厭煩，如果添加一些靈活多變的成分，生活便會變得有意思起來。不斷追尋、不斷靠近目標(biāo)的日子，才更有意義！

二 窮舉解法

下面結(jié)合一道經(jīng)典的題目：最大子數(shù)組的和，對比暴力枚舉解法和動態(tài)規(guī)劃解法，進而體會動態(tài)規(guī)劃的魅力。

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4]

輸出: 6

解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

就此題而言，原問題是??[-2,1,-3,4,-1,2,1,-5,4] ，

子問題如?[-2]，[1,-3]，[-2,1,-3]，[4,-1,2,-5]，相應(yīng)的最大和為：-2，1，1，4，

它們都是可行解，但不是最優(yōu)解。一共可能的子序列有：n + n*(n-1) / 2 ，對于數(shù)組長度為n的問題，暴力求解的時間復(fù)雜度為：O(n^2)，即窮舉所有子序列，找出最大和。

三?初識動態(tài)規(guī)劃

動態(tài)規(guī)劃的基本思想通俗來說，要想求原問題的最優(yōu)解，只需要求得子問題的最優(yōu)解，組合子問題最優(yōu)解，進而得到原問題的最優(yōu)解。

某個問題是否能應(yīng)用動態(tài)規(guī)劃，通常需要滿足3個條件：

1. 最優(yōu)子結(jié)構(gòu)

2. 后續(xù)狀態(tài)無關(guān)性

3. 重復(fù)子問題

這些太理論了，尤其初次接觸動態(tài)規(guī)劃，看到這些會很懵。接下來，我會通過實例，進一步形象化解釋這三個條件。?

如果確認(rèn)問題滿足這三個條件后，下一步就是去尋找狀態(tài)相關(guān)的決策或策略，此策略如果能在原問題上求得最優(yōu)解，必然也能使用此策略，求得子問題的最優(yōu)解。如果不成立，表明策略是失敗的。

下面先來判斷，這個問題適不適合動態(tài)規(guī)劃求解。

四 最優(yōu)子結(jié)構(gòu)

下面是原問題：

為了求得最優(yōu)解，能不能先求解下面藍(lán)色區(qū)域表示的子序列的最優(yōu)解？

如果藍(lán)色色塊的最大和是如下紫色連續(xù)區(qū)域：

那么，考慮上最后一個色塊4后，同時比較：包括-5元素在內(nèi)的最大和如果大于紫色色塊的和，那么最大和包括色塊4，否則不會包括色塊4，就是原來的紫色色塊 ：

所以只需求得子問題的最優(yōu)解后，原問題的最優(yōu)解便能推導(dǎo)出來，這表明此問題具備最有子結(jié)構(gòu)性質(zhì)！

五?后續(xù)狀態(tài)無關(guān)性

能夠應(yīng)用動態(tài)規(guī)劃算法的另一個前提：后續(xù)狀態(tài)無關(guān)性，這個問題很明顯，如下藍(lán)色色塊區(qū)域，子數(shù)組的最大和，與后面的紅色色塊無關(guān)：

因此，子序列的最大和問題，具備后續(xù)狀態(tài)無關(guān)性。

六 重復(fù)子問題

如下是以-2為根節(jié)點的，可能連續(xù)搜索子路徑：

如下是以1為根節(jié)點，可能的連續(xù)搜索子路徑：

任意選取一條以-2為根的子路徑：[-2, 1,-3,4]，和以1為根的子路徑[1,-3,4]，求出子路徑[-2, 1,-3,4]的連續(xù)最大和，后面又去求解子問題[1,-3,4]的連續(xù)最大和，然而，相對于子問題[-2, 1,-3,4]而言，[1,-3,4]是原來問題的子子問題，沒有必要再去求解，因為求解子問題[-2, 1,-3,4]的最優(yōu)解時，一定會考慮子子序列[1,-3,4]，否則求解[-2, 1,-3,4]就是錯誤的。

綜上，使用暴力枚舉會對很多重復(fù)子問題計算，也就是說這個問題具備重復(fù)子問題特性！

七 應(yīng)用動態(tài)規(guī)劃求解

滿足以上三個基本條件后，確定可以使用動態(tài)規(guī)劃，而強大的動態(tài)規(guī)劃，能將以上問題時間復(fù)雜度降到 O(n)。

卡內(nèi)基梅大學(xué)一位教授首先提出此動態(tài)規(guī)劃的解法，命名為 Kadane's algorithm，Kadane算法使用的決策策略，非常巧妙，非常簡潔：

current_sum?= max(x, x + current_sum)

其中 current_sum 初始值為：負(fù)無窮

上面策略表達(dá)的含義：?

如果 current_sum 小于 0，則更新current_sum 值為當(dāng)前迭代到的元素值 x；

如果 current_sum 不小于 0，則 current_sum 值同時吸納 x 和上一時步的 current_sum，

所以，無論 current_sum 大小，當(dāng)前迭代到?x 值總是會被吸納到 current_sum 中，這個策略保證了是連續(xù)的子數(shù)組，

如果再發(fā)揮想象力，把 current_sum 定義為最大貢獻(xiàn)值，如果上一個迭代步的最大貢獻(xiàn)值大于0，就會把它吸納到當(dāng)前步的current_sum中，否則當(dāng)前步的current_sum值不會吸納之前迭代步的current_sum，只保留當(dāng)前元素 x 值。

基于此更新策略，能夠求出任意一個迭代步的 current_sum，就題目中給定的數(shù)組：[-2,1,-3,4,-1,2,1,-5,4]，

初始狀態(tài)，current_sum = float('-inf')?

i = 0, x = -2, current_sum = -2?

i = 1, x = 1,? current_sum = max(1, 1-2) = 1

i = 2, x = -3, current_sum = max(-3, -3+1) = -2

i = 3, x = 4, current_sum = max(4, 4-2) = 4

i = 4, x = -1, current_sum = max(-1, -1+4) = 3

i = 5, x = 2, current_sum = max(2, 2+3) = 5

i = 6, x = 1, current_sum = max(1, 1+5) =?6

i = 7, x = -5, current_sum = max(-5, -5+6) = 1

i = 8, x = 4, current_sum = max(4, 4+1) = 5

從中選擇最大的current_sum，便是原問題的最優(yōu)解，即為 6

八 代碼

class?Solution:
????def?maxSubArray(self,?nums:?List[int])?->?int:
????????current_sum,?best_sum?=?float('-inf'),?float('-inf')

????????for?num?in?nums:
????????????current_sum?=?max(num,?num?+?current_sum)
????????????best_sum?=?max(current_sum,?best_sum)
????????
????????return?best_sum

輸入：[-10,9,20,null,null,15,7]

?  -10
? ?/ \
? 9 ?20
? ? / ?\
? ?15 ? 7

輸出：42