[[387482]]

 本人看了vivo，阿里巴巴的校招算法題，可以明確知道絕對(duì)有動(dòng)態(tài)規(guī)劃。如果沒(méi)有，那么出題的面試官真的沒(méi)有水平。跌了N次的動(dòng)態(tài)規(guī)劃，Runsen最近也拼命搞動(dòng)態(tài)規(guī)劃。這篇文章浪費(fèi)了三天時(shí)間。

看了Leetcode公眾號(hào)的文章：https://mp.weixin.qq.com/s/rhyUb7d8IL8UW1IosoE34g

極客時(shí)間超哥的動(dòng)態(tài)規(guī)劃、拉勾教育的算法專欄。Runsen真的不想在動(dòng)態(tài)規(guī)劃，死一次又一次。死了N次，學(xué)了N次，就是他媽的寫(xiě)不出來(lái)。

動(dòng)態(tài)規(guī)劃需要搞定三個(gè)系列：三個(gè)背包，零錢(qián)問(wèn)題和股票問(wèn)題。今天，Runsen就開(kāi)始干掉最重要的「背包問(wèn)題」。

三個(gè)背包問(wèn)題：01背包，多重背包，完全背包。

動(dòng)態(tài)規(guī)劃前置知識(shí)

動(dòng)態(tài)規(guī)劃的名詞

「狀態(tài)轉(zhuǎn)移方程」：比如Runsen們一般看到的狀態(tài)轉(zhuǎn)移方程：dp[n] = dp[n-1] + dp[n-2]。

「最優(yōu)子結(jié)構(gòu)：一般由最優(yōu)子結(jié)構(gòu)，推導(dǎo)出一個(gè)狀態(tài)轉(zhuǎn)移方程 f(n)，就能很快寫(xiě)出問(wèn)題的遞歸實(shí)現(xiàn)方法。把大問(wèn)題變成幾個(gè)小問(wèn)題，在幾個(gè)小問(wèn)題中求出最佳解?！?/p>

「重疊子問(wèn)題：比如斐波那契數(shù)列中的f(5)，算了f(4)和f(3)，結(jié)果f(4)又給Runsen算了一次f(3)。其實(shí)就是將一棵二叉樹(shù)進(jìn)行剪枝操作，方法是備忘錄來(lái)存儲(chǔ)在內(nèi)存上?！?/p>

「自下而上：反過(guò)來(lái)求解」

動(dòng)態(tài)規(guī)劃思路

動(dòng)態(tài)規(guī)劃是一種求問(wèn)題最優(yōu)解的方法。通用的思路：將問(wèn)題的解轉(zhuǎn)化成==> 求解子問(wèn)題，==> 遞推，==>最小子問(wèn)題為可直接獲得的初始狀態(tài)。

詳細(xì)的步驟下面所示：

判斷是否可用遞歸來(lái)解，可以的話進(jìn)入步驟 2

分析在遞歸的過(guò)程中是否存在大量的重復(fù)子問(wèn)題

采用備忘錄的方式來(lái)存子問(wèn)題的解以避免大量的重復(fù)計(jì)算(剪枝)

改用自底向上的方式來(lái)遞推，即動(dòng)態(tài)規(guī)劃

關(guān)鍵就是「找狀態(tài)轉(zhuǎn)移方程」。

斐波那契數(shù)列和爬樓梯問(wèn)題

斐波那契數(shù)列最早從兔子問(wèn)題演變過(guò)來(lái)的，

假設(shè)一對(duì)初生兔子一個(gè)月到成熟期，一對(duì)成熟兔子每月生一對(duì)兔子，并且一年內(nèi)沒(méi)有發(fā)生死亡。那么，由一對(duì)初生兔子開(kāi)始 一年以后可以繁殖多少對(duì)兔子?

我們直接看下面的圖

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

發(fā)現(xiàn)以上規(guī)律是，每月的兔子對(duì)數(shù)=上一月的兔子對(duì)數(shù)+該月新生的兔子對(duì)數(shù)=上一月的兔子對(duì)數(shù)+上上月的兔子對(duì)數(shù)

得到序列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

這個(gè)序列即為斐波那契數(shù)列“(Fibonacci sequence)”。斐波那契數(shù)列中的任一個(gè)數(shù)，都叫斐波那契數(shù)

斐波那契數(shù)列，通常都是用來(lái)講解遞歸函數(shù)，嘗試用遞歸的思路來(lái)解決，但是時(shí)間復(fù)雜度高達(dá)。

def fib(n): 
  if n <= 1: 
      return 1 
  return fib(n-1) + fib(n-2) 
 
for i in range(20): 
    print(fib(i), end=' ') 

但是，我們發(fā)現(xiàn)時(shí)間復(fù)雜度高達(dá)，最主要的原因是存在重復(fù)計(jì)算。比如fib(3) 會(huì)計(jì)算 fib(2) + fib(1)， 而 fib(2) 又會(huì)計(jì)算 fib(1) + fib(0)。

這個(gè) fib(1) 就是完全重復(fù)的計(jì)算，不應(yīng)該為它再遞歸調(diào)用一次，而是應(yīng)該在第一次求解除它了以后，就把他“記憶”下來(lái)。

這就是備忘錄解法，用空間來(lái)?yè)Q取時(shí)間的思路。把已經(jīng)求得的解放在字典Map或者列表list 里，下次直接取，而不去重復(fù)結(jié)算。

備忘錄解法的代碼和動(dòng)態(tài)規(guī)劃的代碼和思路基本一致。

斐波那契數(shù)列在Leetcode也有一題類似的，這是Leetcode第70題. 爬樓梯，每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢?

注意：給定 n 是一個(gè)正整數(shù)。

輸入：2 
輸出：2 
解釋： 有兩種方法可以爬到樓頂。 
1.  1 階 + 1 階 
2.  2 階 

斐波那契數(shù)列和爬樓梯問(wèn)題的狀態(tài)轉(zhuǎn)移方程都是:dp[i] = dp[i-1] +dp[i-2]。但是需要初始化dp，不然回報(bào)list assignment index out of range的錯(cuò)誤。

下面就是斐波那契數(shù)列問(wèn)題 爬樓梯的解決代碼，也是Leetcode70題的解決代碼。

class Solution: 
    def Fibonacci(self, n): 
        if n == 0: 
            return 1 
        if n == 1: 
            return 1 
        if n > 1: 
            dp = [0] * (n+1) 
            dp[0] = 1  
            dp[1]= 1 
            for i in range(2,n+1): 
                dp[i] = dp[i-1] +dp[i-2] 
            return dp[n] 

Leetcode53 最大子序和

最大子序和，Runsen記得很清楚是Leetcode的53題。

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

聲明兩個(gè)變量, currentSum: 之前連續(xù)幾個(gè)值相加的和, maxSum: 當(dāng)前最大的子序列和。最大子序和狀態(tài)轉(zhuǎn)移方程 f(i) = max(f(i), f(i)+nums[i+1])

def maxSubArray(nums) : 
    '''查找連續(xù)子數(shù)組的最大和 
 
    Args: 
        nums: 整數(shù)數(shù)組 
 
    Returns: 
        返回整數(shù)數(shù)組的最大子序和 
    ''' 
    # 比較當(dāng)前子序和，最大子序和，返回最大值 
 
    # 定義當(dāng)前子序和以及最大子序和為第一個(gè)元素 
    cursum = maxsum = nums[0] 
    for i in range(1, len(nums)): 
        cursum = max(nums[i], cursum + nums[i]) 
        print(cursum) 
        # 比較當(dāng)前值和定義的最大子序和值，將最大值重置賦值給 max_sum 
        maxsum = max(cursum, maxsum) 
        print(maxsum) 
    return maxsum 
 
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])) 

前面只是動(dòng)態(tài)規(guī)劃的熱身，Runsen先進(jìn)入「三個(gè)背包問(wèn)題的強(qiáng)化系列」，01背包問(wèn)題才是動(dòng)態(tài)規(guī)劃的入門(mén)階段。

01背包問(wèn)題

對(duì)應(yīng)的題目：https://www.acwing.com/problem/content/2/

01背包問(wèn)題就是物品只有一件。

輸入格式 : 第一行兩個(gè)整數(shù)，N，V，用空格隔開(kāi)，分別表示物品數(shù)量和背包容積。接下來(lái)有 N 行，每行兩個(gè)整數(shù) vi,wi，用空格隔開(kāi)，分別表示第 i 件物品的體積和價(jià)值。  
輸出格式 : 輸出一個(gè)整數(shù)，表示最大價(jià)值。  
數(shù)據(jù)范圍 : 0<N,V≤1000  ；0<vi,wi≤1000 

 輸入樣例

4 5 
1 2 
2 4 
3 4 
4 6 

輸出樣例：

8 # 4+4 2+6 

在解決這類問(wèn)題先，dp怎么定義和狀態(tài)轉(zhuǎn)移方程怎么搞就是重要，搞定了就是半分鐘的事情。搞不定了可能半小時(shí)的事情。

很多人和Runsen一樣，都會(huì)把狀態(tài)定義二維數(shù)組：為前i「?jìng)€(gè)」 物品中，體積恰好為v 時(shí)的最大價(jià)值。

狀態(tài)轉(zhuǎn)移方程也是順便搞定：

如果 「不選第 i 個(gè)物品」，那么前 i 個(gè)背包的最大價(jià)值就是前 i-1 個(gè)物品的價(jià)值，即 dp[i][j] = dp[i-1][j];

如果 「選擇了第 i 個(gè)物品」，前 i-1 個(gè)物品的體積就是j - weight[i]，狀態(tài)方程為 dp[i - 1][j - weight[i]] + value[i]，注意這時(shí)的價(jià)值是前i-1個(gè)物品的價(jià)值，因此少了 weight[i]]的空間，所以 dp[i - 1][j - weight[i]] + value[i]。

''' 
@Author：Runsen 
@WeChat：RunsenLiu  
@微信公眾號(hào)：Python之王 
@CSDN：https://blog.csdn.net/weixin_44510615 
@Github：https://github.com/MaoliRUNsen 
@Date：2020/9/10 
''' 
# n是個(gè)數(shù) v是體積  # 4 5 
n, v = map(int, input().split()) 
goods = [] 
for i in range(n): 
    goods.append([int(i) for i in input().split()]) 
 
# 初始化，先全部賦值為0，這樣至少體積為0或者不選任何物品的時(shí)候是滿足要求 
# 因?yàn)?span id="5jnfyyd"    class="keyword">for 循環(huán)先遍歷個(gè)數(shù)，所以將體積寫(xiě)在里面 
dp = [[0 for i in range(v+1)] for j in range(n+1)] 
print(goods) # [[1, 2], [2, 3], [3, 4], [4, 5]] 
# 0 可以無(wú)視掉 
for i in range(1, n+1): 
    for j in range(1,v+1): 
        # 判斷背包容量是不是大于第i件物品的體積 
        if j>=goods[i-1][0]: 
            # 在選和不選的情況中選出最大值 
            dp[i][j] = max(dp[i-1][j], dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1]) 
        else: 
            # 第i個(gè)物品不選 
            dp[i][j] = dp[i-1][j]   
print(dp) 
print(dp[-1][-1]) 
 
# 測(cè)試數(shù)據(jù) 
5 10 
1 2 
2 3 
3 4 
4 5 
5 6 
[[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]] 
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], [0, 2, 3, 5, 5, 5, 5, 5, 5, 5, 5], [0, 2, 3, 5, 6, 7, 9, 9, 9, 9, 9], [0, 2, 3, 5, 6, 7, 9, 10, 11, 12, 14], [0, 2, 3, 5, 6, 7, 9, 10, 11, 12, 14]] 
14  # 2+3+4+5 

上面代碼，如果知道了dp怎么定義和狀態(tài)轉(zhuǎn)移方程，那么和Runsen寫(xiě)的一樣快，其實(shí)那時(shí)Runsen寫(xiě)得挺慢得，說(shuō)不定你比Runsen還厲害。

上面的代碼是狀態(tài)定義二維數(shù)組，有的大佬竟然可以把狀態(tài)定義一維數(shù)組，這樣空間就節(jié)省了。「Runsen都百思不知其解」。只能說(shuō)Runsen真的挺菜的。只好勤能補(bǔ)拙!

一維數(shù)組就是去掉了狀態(tài)，且的遍歷方式改為 「倒序」 遍歷到 c[i]。

因此，Runsen們可以將求解空間進(jìn)行優(yōu)化，將二維數(shù)組壓縮成一維數(shù)組，此時(shí)，轉(zhuǎn)移方程變?yōu)椋?/p>

''' 
@Author：Runsen 
@WeChat：RunsenLiu  
@微信公眾號(hào)：Python之王 
@CSDN：https://blog.csdn.net/weixin_44510615 
@Github：https://github.com/MaoliRUNsen 
@Date：2020/9/10 
''' 
n, v = map(int, input().split()) 
goods = [] 
for i in range(n): 
    goods.append([int(i) for i in input().split()]) 
print(goods) # [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]] 
dp = [0 for i in range(v + 1)] 
for i in range(n): 
    # 由于要放入物品，所以從空間v開(kāi)始遍歷到0 
    for j in range(v, -1, -1): 
        # 判斷背包容量是不是大于第i件物品的體積 
        if j >= goods[i][0]: 
            # 更新j的狀態(tài)，即當(dāng)前容量放入物品之后的狀態(tài) 
            dp[j] = max(dp[j], dp[j - goods[i][0]] + goods[i][1]) 
print(dp) 
print(dp[-1]) 
 
5 10 
1 2 
2 3 
3 4 
4 5 
5 6 
[[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]] 
[0, 2, 3, 5, 6, 7, 9, 10, 11, 12, 14] 
14 

上面就是01背包的最終解決方法，由于文章有限，多重背包，完全背包將在之后的博客進(jìn)行書(shū)寫(xiě)!!!

不知不覺(jué)現(xiàn)在寫(xiě)了幾天，代碼反復(fù)寫(xiě)，寫(xiě)完寫(xiě)博客，真心累!誰(shuí)叫自己的算法比較弱!

希望以后遇到01背包的問(wèn)題，就是在恐怖的算法面試中遇見(jiàn)了Runsen的愛(ài)情!

參考資料

[1]傳送門(mén)~:https://github.com/MaoliRUNsen/runsenlearnpy100