2.1斐波那契數列問題
2.2矩陣系列問題
2.3跳躍系列問題
3.1 01揹包
3.2 完全揹包
3.3多重揹包
3.4 一些變形選講
2.1斐波那契系列問題
在數學上，斐波納契數列以如下被以遞歸的方法定義：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）根據定義，前十項為1, 1, 2, 3, 5, 8, 13, 21, 34, 55
例1：給定一個正整數n，求出斐波那契數列第n項（這時n較小）
解法一：完全抄定義
def f(n):
if n==1 or n==2:
return 1
return f(n-1)+f(n-2)
分析一下，為什麼說遞歸效率很低呢？咱們來試著運行一下就知道了：
比如想求f(10)，計算機裡怎麼運行的？
想算出f(10)，就要先算出F(9),
想算出f(9)，就要先算出F(8),
想算出f(8)，就要先算出F(7),
想算出f(7)，就要先算出F(6)……
兜了一圈，我們發現，有相當多的計算都重複了，比如紅框部分：
那如何解決這個問題呢？問題的原因就在於，我們算出來某個結果，並沒有記錄下來，導致了重複計算。那很容易想到如果我們把計算的結果全都保存下來，按照一定的順序推出n項，就可以提升效率
解法2：
def f1(n):
if n==1 or n==2:
return 1
l=[0]*n #保存結果
l[0],l[1]=1,1 #賦初值
for i in range(2,n):
l[i]=l[i-1]+l[i-2] #直接利用之前結果
return l[-1]
可以看出，時間o(n)，空間o(n)。
繼續思考，既然只求第n項，而斐波那契又嚴格依賴前兩項，那我們何必記錄那麼多值浪費空間呢？只記錄前兩項就可以了。
解法3：
def f2(n):
a,b=1,1
for i in range(n-1):
a,b=b,a+b
return a
補充：
pat、藍橋杯等比賽原題：求的n很大，F(N)模一個數。應每個結果都對這個數取模，否則：第一，計算量巨大，浪費時間；第二，數據太大，爆內存，
對於有多組輸入並且所求結果類似的題，可以先求出所有結果存起來，然後直接接受每一個元素，在表中查找相應答案
此題有快速冪算法，但是礙於篇幅和同學們水平有限，不再敘述，可以自行學習。
例2：一隻青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
依舊是找遞推關係：
1）跳一階，就一種方法
2）跳兩階，它可以一次跳兩個，也可以一個一個跳，所以有兩種
3）三個及三個以上，假設為n階，青蛙可以是跳一階來到這裡，或者跳兩階來到這裡，只有這兩種方法。
它跳一階來到這裡，說明它上一次跳到n-1階，
同理，它也可以從n-2跳過來
f（n）為跳到n的方法數，所以，f(n)=f(n-1)+f(n-2)
優化思路與例1類似，請自行思考。
例3：我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
N=1: 只有一種
N=2，兩種:
N=3:
讀到這裡，你們應該能很快想到，依舊是斐波那契式遞歸啊。
對於n>=3:怎麼能覆蓋到三？
只有兩種辦法，從n-1的地方豎著放了一塊，或者從n-2的位置橫著放了兩塊
例4：給定一個由0-9組成的字符串，1可以轉化成A，2可以轉化成B。依此類推。。25可以轉化成Y，26可以轉化成z，給一個字符串，返回能轉化的字母串的有幾種？
比如：123，可以轉化成
1 、2 、3變成ABC，
12 、3變成LC，
1 、23變成AW
三種，返回三，
比如99999，就一種：iiiii，返回一。
分析：求i位置及之前字符能轉化多少種。
兩種轉化方法
1）字符i自己轉換成自己對應的字母
2）和前面那個數組成兩位數，然後轉換成對應的字母
假設遍歷到i位置，判斷i-1位置和i位置組成的兩位數是否大於26，大於就沒有第二種方法，f(i)=f(i-1),如果小於26， f(i)=f(i-1)+f(i-2)
2.2矩陣系列問題
例5：給一個由數字組成的矩陣，初始在左上角，要求每次只能向下或向右移動，路徑和就是經過的數字全部加起來，求可能的最小路徑和。
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
路徑：1 3 1 0 6 1 0路徑和最小，返回12
分析：我們可以像之前一樣，暴力的把每一種情況都試一次，但是依舊會造成過多的重複計算，以本題為例子最後解釋一下暴力慢在哪裡，以後不再敘述了。
比如本題來講，我們嘗試如下路徑：
有很多路是重複走過的一遍。
再進一步說：
從1到6位置，有很多路可以走，直觀感受一下：
所有路中，一定會有和最小的，但是我們並不知道，每次嘗試一次1->6->終點的路線時，我們把所有的情況都算了一遍，這過程中我們浪費了相當多的有效信息。
這就是暴力的結果。
優化做法：生成和矩陣相同大小的二維表，用來記錄到起點每個位置的最小路徑和
接下來帶著大家真正進入動態規劃；
第一步：初始化（對於本題來說，第一列和第一行，我們別無選擇，就一條路，因此，我們可以直接確定答案）
第二步：確定其餘位置如何推出（我們稱為狀態轉移方程）
直觀來說，每個位置只可能是從上面，或者左邊走來的：
對於普遍的位置i，j，只有i-1,j和i,j-1這兩個位置可以一步走到這裡，所以
DP[i,j]=min(DP[i,j-1],DP[i-1,j]）+L[i,j]（之前的最優解加上本位置的數字）
繼續優化：和之前一樣，這個式子實際上也是嚴格依賴兩個值，一個是左邊的值，一個是上面的值，所以，我們按之前的思路，應該可以想到可以壓縮空間。
我們嘗試用一維的空間來解題：
想象這是我們的第一行答案：
我們如何利用僅有的一維空間來更新出下一行呢？
我們要想：
我們需要左面的數字，所以，本位置的左邊必須是更新過的數字（否則就是左上的位置了），所以應該從左往右更新。
我們需要上面的數字，這個不需要更新，本來就需要本位置的舊數字。
本題第二行為：8，1，3，4
第一行答案為
依次更新：
更新A：
（只能向下走）
更新B：
（比較從左邊來和從上面來哪裡比較小）
更新C：
更新D：
最後我們可以發現，偽代碼是這樣的：
For i 0 -> 高度:
For j 0 -> 寬度
DP[j]=min(DP[j-1],DP[j]）+L[i,j]
時間不變，空間優化到o(min（高，寬））
例6：給一個由數字組成的矩陣，初始在左上角，要求每次只能向下或向右移動，路徑和就是經過的數字全部加起來，求可能的最大路徑和。
和例5只差一個“大”字，請自己思考
例7：一個矩陣，初始在左上角，要求每次只能向下或向右移動，求到終點的方法數。
和例5，6類似，只是方法數應該等於，左邊的方法數加上上面的方法數
第二章末練習
1
一個只包含'A'、'B'和'C'的字符串，如果存在某一段長度為3的連續子串中恰好'A'、'B'和'C'各有一個，那麼這個字符串就是純淨的，否則這個字符串就是暗黑的。例如：
BAACAACCBAAA 連續子串"CBA"中包含了'A','B','C'各一個，所以是純淨的字符串
AABBCCAABB 不存在一個長度為3的連續子串包含'A','B','C',所以是暗黑的字符串
你的任務就是計算出長度為n的字符串(只包含'A'、'B'和'C')，有多少個是暗黑的字符串。(網易17校招原題)
2、X國的一段古城牆的頂端可以看成 2*N個格子組成的矩形（如下圖所示），現需要把這些格子刷上保護漆。
你可以從任意一個格子刷起，刷完一格，可以移動到和它相鄰的格子（對角相鄰也算數），但不能移動到較遠的格子（因為油漆未乾不能踩！）
比如：a d b c e f 就是合格的刷漆順序。
c e f d a b 是另一種合適的方案。
當已知 N 時，求總的方案數。當N較大時，結果會迅速增大，請把結果對 1000000007 (十億零七) 取模。
3.1 01揹包
入門了動態規劃之後，我們來看一個經典系列問題：揹包問題
這是最基礎的揹包問題，特點是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態：
f[i][j]表示前i件物品恰放入一個容量為j的揹包可以獲得的最大價值。則其狀態轉移方程為：
“將前i件物品放入容量為j的揹包中”這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i−1件物品的問題。
如果不放第i件物品，那麼問題就轉化為“前i−1件物品放入容量為j的揹包中”，價值為f[i−1][j]；
如果放第i件物品，那麼問題就轉化為“前i−1件物品放入剩下的容量為j−c[i]的揹包中”，此時能獲得的最大價值就是f[i−1][j−w[i]],再加上通過放入第i件物品獲得的價值v[i]。
因此得出上面的式子。
繼續優化空間（利用之前提到的知識）：
如果我們壓縮到一維空間解題，這次我們需要的是上面的位置和左上的位置，也就是說，我們需要左邊的位置是沒被更新過的，得出更新順序應該從右往左：
for i in range(1,n+1):
for j in range(v,-1,-1)
f[j] = max(f[j], f[j - w[i]] + v[i]);
3.2 完全揹包
這個問題非常類似於01揹包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已並非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01揹包時的思路,很容易得出：
這跟01揹包問題一樣有O(VN)個狀態需要求解，但求解每個狀態的時間已經不是常數了
而是，總的複雜度可以認為是,將01揹包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01揹包問題的方程的確是很重要，可以推及其它類型的揹包問題。但我們還是試圖改進這個複雜度。
我們可以知道，對於一個普遍位置w，當前物品代價為2的話，下圖中紅色區域就是和位置w的取值相關的一些數值：
對當前物品的決策就依次是：不拿、拿一個、拿兩個、拿三個（對應上面式子中的k）
我們算法優化的思路就是不斷去除重複計算，顯然我們可以繼續優化這個式子。
請思考：我們的E3位置是如何得出的？其實是根據三個紅色區域得出的，但是我們算位置w時又算了一遍，顯然是重複了。而E3其實包含了不拿、拿一個、拿兩個這些情況中的最優解，我們算w時直接用就可以了。
給出模板代碼：
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= V; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
對比兩種揹包：
這個代碼與01揹包的代碼只有j的循環次序不同而已。為什麼這樣一改就可行呢？
首先想想為什麼01揹包中要按照j=V...0 j=V...0j=V...0的逆序來循環。這是因為要保證第i次循環中的狀態f[i][j]是由狀態f[i−1][j−w[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[i−1][j−w[i]]。
而現在完全揹包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i ii種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結果f[i][j−w[i]]，所以就可以並且必須採用j=0...V j=0...Vj=0...V的順序循環。這就是這個簡單的程序為何成立的道理。
最終給出狀態轉移方程給不明白的同學看：
（也可以通過數學導出此式）
3.3多重揹包
和之前的揹包不同，每種物品不是隻有一件，也不是有無限件，這次的每種物品的數量都是有限制的，我們對於每種物品，可以選擇拿一件、兩件……p[i]件。
我們借用上一種問題的圖：
看起來是類似的，位置w依舊和紅色區域相關，但是我們可以直接根據E3來求出位置w嗎？是不能的，因為條件變了，每種物品不是無限的，可能在w位置，圖中橢圓圈出的位置代表著需要拿三個，但是如果規定最多拿兩個，我們這種算法就出問題了。
一種做題思路：把每個物品都按01揹包做：比如第i種物品，我們就按有p[i]件相同的物品。每一種物品都是如此，按01揹包做就可以了。（但是顯然很蠢）
改進：
我們平時買東西時，難道帶的全是一元的硬幣嗎？當然不是，只要手中的錢可以湊出商品的價格即可，比如9元的東西，我不一定用九個硬幣（揹包問題的物品）來付錢，可以5元+4個1元。
揹包問題也一樣，我們不一定要全部拆成1的物品，只要我們的物品可以代表0——>p[i]的所有情況，我們就認為這種策略是正確的。
那如何拆p[i]個物品可以保證我們的物品可以代表0——>p[i]的所有情況呢？這裡要藉助2進制思想。
一個n位的二進制數可以取0到2的n次方-1，第i位代表的是2的i-1次方。
對應到物品：
我們的p[i]=15，我們怎樣拆呢？
1+2+4+8即可，這四個數一定可以組合出0-15的任何一個數。
二進制拆分代碼如下：
for (int i = 1; i <= n; i++) {
int num = min(p[i], V / w[i]);
for (int k = 1; num > 0; k <<= 1) {
if (k > num) k = num;
num -= k;
for (int j = V; j >= w[i] * k; j--)
f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
}
}
3.4 一些變形選講
1）最常見的一些變形，甚至不能說是變形，上面也提到過，但是怕同學們不知道：
我們常見的問題中，一般是問最優解，可能是最大，或者最小，但是，問題也可能是方法的數量，這個時候，一般把狀態轉移方程中的max(min)改為sum（求和）即可，當然，壓縮空間後的樣子還是需要自己寫。
2）初始化的細節問題
我們看到的求最優解的揹包問題題目中，事實上有兩種不太相同的問法。有的題目要求"恰好裝滿揹包"時的最優解，有的題目則並沒有要求必須把揹包裝滿。這兩種問法的區別是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿揹包，那麼在初始化時除了f[0]為0其它f[1...V]均設為−∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿揹包的最優解。
如果並沒有要求必須把揹包裝滿，而是隻希望價格儘量大，初始化時應該將f[0...V]全部設為0。
為什麼呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入揹包時的合法狀態。如果要求揹包恰好裝滿，那麼此時只有容量為0的揹包可能被價值為0的nothing “恰好裝滿”，其它容量的揹包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是
−∞了。如果揹包並非必須被裝滿，那麼任何容量的揹包都有一個合法解“什麼都不裝”，這個解的價值為0，所以初始時狀態的值也就全部為0了。
3）常數優化
前面的代碼中有for(j=V...w[i])，還可以將這個循環的下限進行改進。
由於只需要最後f[j]的值，倒推前一個物品，其實只要知道f[j−w[n]]即可。以此類推，對以第j個揹包，其實只需要知道到f[j−sumw[j...n]]即可，代碼自行修改。
4）其實拆解二進制物品並不是多重揹包的最優解，但是最優的單調隊列思想寫起來有些繁瑣，可能以後會寫。
————————————————
通過分享實用的計算機編程語言乾貨，推動中國編程到2025年基本實現普及化，使編程變得全民皆知，最終實現中國編程之崛起，這裡是中國編程2025，感謝大家的支持。
原文鏈接：https://blog.csdn.net/hebtu666/article/details/100585136
原文鏈接：https://blog.csdn.net/qq_38456809/article/details/102942561
閱讀更多 中國編程2025 的文章
