[[387482]]

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

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

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

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

三個背包問題：01背包，多重背包，完全背包。

動態(tài)規(guī)劃前置知識

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

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

「最優(yōu)子結構：一般由最優(yōu)子結構，推導出一個狀態(tài)轉(zhuǎn)移方程 f(n)，就能很快寫出問題的遞歸實現(xiàn)方法。把大問題變成幾個小問題，在幾個小問題中求出最佳解。」

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

「自下而上：反過來求解」

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

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

詳細的步驟下面所示：

判斷是否可用遞歸來解，可以的話進入步驟 2

分析在遞歸的過程中是否存在大量的重復子問題

采用備忘錄的方式來存子問題的解以避免大量的重復計算(剪枝)

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

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

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

斐波那契數(shù)列最早從兔子問題演變過來的，

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

我們直接看下面的圖

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

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

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

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

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

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)時間復雜度高達，最主要的原因是存在重復計算。比如fib(3) 會計算 fib(2) + fib(1)， 而 fib(2) 又會計算 fib(1) + fib(0)。

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

這就是備忘錄解法，用空間來換取時間的思路。把已經(jīng)求得的解放在字典Map或者列表list 里，下次直接取，而不去重復結算。

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

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

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

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

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

下面就是斐波那契數(shù)列問題 爬樓梯的解決代碼，也是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。 

聲明兩個變量, currentSum: 之前連續(xù)幾個值相加的和, maxSum: 當前最大的子序列和。最大子序和狀態(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ù)組的最大子序和 
    ''' 
    # 比較當前子序和，最大子序和，返回最大值 
 
    # 定義當前子序和以及最大子序和為第一個元素 
    cursum = maxsum = nums[0] 
    for i in range(1, len(nums)): 
        cursum = max(nums[i], cursum + nums[i]) 
        print(cursum) 
        # 比較當前值和定義的最大子序和值，將最大值重置賦值給 max_sum 
        maxsum = max(cursum, maxsum) 
        print(maxsum) 
    return maxsum 
 
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])) 

前面只是動態(tài)規(guī)劃的熱身，Runsen先進入「三個背包問題的強化系列」，01背包問題才是動態(tài)規(guī)劃的入門階段。

01背包問題

對應的題目：https://www.acwing.com/problem/content/2/

01背包問題就是物品只有一件。

輸入格式 : 第一行兩個整數(shù)，N，V，用空格隔開，分別表示物品數(shù)量和背包容積。接下來有 N 行，每行兩個整數(shù) vi,wi，用空格隔開，分別表示第 i 件物品的體積和價值。  
輸出格式 : 輸出一個整數(shù)，表示最大價值。  
數(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 

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

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

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

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

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

''' 
@Author：Runsen 
@WeChat：RunsenLiu  
@微信公眾號：Python之王 
@CSDN：https://blog.csdn.net/weixin_44510615 
@Github：https://github.com/MaoliRUNsen 
@Date：2020/9/10 
''' 
# n是個數(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或者不選任何物品的時候是滿足要求 
# 因為for 循環(huán)先遍歷個數(shù)，所以將體積寫在里面 
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 可以無視掉 
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個物品不選 
            dp[i][j] = dp[i-1][j]   
print(dp) 
print(dp[-1][-1]) 
 
# 測試數(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寫的一樣快，其實那時Runsen寫得挺慢得，說不定你比Runsen還厲害。

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

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

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

''' 
@Author：Runsen 
@WeChat：RunsenLiu  
@微信公眾號：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開始遍歷到0 
    for j in range(v, -1, -1): 
        # 判斷背包容量是不是大于第i件物品的體積 
        if j >= goods[i][0]: 
            # 更新j的狀態(tài)，即當前容量放入物品之后的狀態(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背包的最終解決方法，由于文章有限，多重背包，完全背包將在之后的博客進行書寫!!!

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

希望以后遇到01背包的問題，就是在恐怖的算法面試中遇見了Runsen的愛情!

參考資料

[1]傳送門~:https://github.com/MaoliRUNsen/runsenlearnpy100