@Author：Runsen

編程的本質來源于算法，而算法的本質來源于數(shù)學，編程只不過將數(shù)學題進行代碼化。 ---- Runsen

本人看了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)轉移方程：比如Runsen們一般看到的狀態(tài)轉移方程：dp[n] = dp[n-1] + dp[n-2]。

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

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

自下而上：反過來求解

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

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

詳細的步驟下面所示：

• 判斷是否可用遞歸來解，可以的話進入步驟 2
• 分析在遞歸的過程中是否存在大量的重復子問題
• 采用備忘錄的方式來存子問題的解以避免大量的重復計算（剪枝）
• 改用自底向上的方式來遞推，即動態(tài)規(guī)劃

關鍵就是找狀態(tài)轉移方程。

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

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

假設一對初生兔子一個月到成熟期，一對成熟兔子每月生一對兔子，并且一年內沒有發(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ù)，嘗試用遞歸的思路來解決，但是時間復雜度高達$O(2^n)$。

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

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

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

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

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

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

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

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

斐波那契數(shù)列和爬樓梯問題的狀態(tài)轉移方程都是: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 1if n == 1:return 1if n > 1:dp = [0] * (n+1)dp[0] = 1 dp[1]= 1for 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)轉移方程 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_summaxsum = max(cursum, maxsum)print(maxsum)return maxsumprint(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ù)據范圍 : 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)轉移方程怎么搞就是重要，搞定了就是半分鐘的事情。搞不定了可能半小時的事情。

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

狀態(tài)轉移方程也是順便搞定：$$dp[i][j]=max(dp[i?1][j],dp[i?1][j?weight[i]]+value[i])$$

如果 「不選第 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ù)據 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)轉移方程，那么和Runsen寫的一樣快，其實那時Runsen寫得挺慢得，說不定你比Runsen還厲害。

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

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

因此，Runsen們可以將求解空間進行優(yōu)化，將二維數(shù)組壓縮成一維數(shù)組，此時，轉移方程變?yōu)?#xff1a;

$$dp(j)=max(dp(j),dp(i?wi)+vi)$$

''' @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開始遍歷到0for 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的愛情！

如果你想跟博主建立親密關系，可以關注博主，或者關注博主公眾號“Python之王”，了解一個非本科程序員是如何成長的。博主ID：潤森（weixin_44510615），希望大家點贊、評論、收藏

本文已收錄 GitHub，傳送門~ ，里面更有大廠面試完整考點，歡迎 Star。

總結

以上是生活随笔為你收集整理的八十八、从斐波那契数列和零一背包问题探究动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。