python做調(diào)查問(wèn)卷網(wǎng)站百度指數(shù)批量
背包問(wèn)題概述
背包問(wèn)題 (Knapsack problem) 是?種組合優(yōu)化的 NP完全問(wèn)題 。
問(wèn)題可以描述為:給定?組物品,每種物品都有??的重量和價(jià)格,在限定的總重量?jī)?nèi),我們?nèi)绾芜x擇,才能使得物品的總價(jià)格最?。
根據(jù)物品的個(gè)數(shù),分為如下?類:
? 01 背包問(wèn)題:每個(gè)物品只有?個(gè)
? 完全背包問(wèn)題:每個(gè)物品有?限多個(gè)
? 多重背包問(wèn)題:每件物品最多有 si 個(gè)
? 混合背包問(wèn)題:每個(gè)物品會(huì)有上?三種情況......
? 分組背包問(wèn)題:物品有 n 組,每組物品?有若?個(gè),每組?最多選?個(gè)物品
其中上述分類??,根據(jù)背包是否裝滿,?分為兩類:
? 不?定裝滿背包
? 背包?定裝滿
優(yōu)化?案:
? 空間優(yōu)化 - 滾動(dòng)數(shù)組
? 單調(diào)隊(duì)列優(yōu)化
? 貪?優(yōu)化
根據(jù)限定條件的個(gè)數(shù),?分為兩類:
? 限定條件只有?個(gè):?如體積 -> 普通的背包問(wèn)題
? 限定條件有兩個(gè):?如體積 + 重量 -> ?維費(fèi)?背包問(wèn)題
根據(jù)不同的問(wèn)法,?分為很多類:
? 輸出?案
? 求?案總數(shù)
? 最優(yōu)?案
? ?案可?性
其實(shí)還有很多分類,但是我們僅需了解即可。因此,背包問(wèn)題種類?常繁多,題型?常豐富,難度也是?常難以捉摸。但是,盡管種類?常多,都是從 01 背包問(wèn)題演化過(guò)來(lái)的。所以,?定要把 01 背包問(wèn)題學(xué)好。
01 背包問(wèn)題
例題一
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
背包問(wèn)題的狀態(tài)表??常經(jīng)典,如果?家不知道怎么來(lái)的,就把它當(dāng)成?個(gè)「模板」記住吧~
我們先解決第?問(wèn):
1. 狀態(tài)表?:
dp[i][j] 表?:從前 i 個(gè)物品中挑選,總體積「不超過(guò)」 j ,所有的選法中,能挑選出來(lái)的最?價(jià)值。
2. 狀態(tài)轉(zhuǎn)移?程:
線性 dp 狀態(tài)轉(zhuǎn)移?程分析?式,?般都是根據(jù)「最后?步」的狀況,來(lái)分情況討論:
i. 不選第 i 個(gè)物品:相當(dāng)于就是去前 i - 1 個(gè)物品中挑選,并且總體積不超過(guò) j 。此時(shí) dp[i][j] = dp[i - 1][j] ;
ii. 選擇第 i 個(gè)物品:那么我就只能去前 i - 1 個(gè)物品中,挑選總體積不超過(guò) j - v[i]的物品。此時(shí) dp[i][j] = dp[i - 1][j - v[i]] + w[i] 。但是這種狀態(tài)不?定存在,因此需要特判?下。
綜上,狀態(tài)轉(zhuǎn)移?程為: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。
3. 初始化:
我們多加??,?便我們的初始化,此時(shí)僅需將第??初始化為 0 即可。因?yàn)槭裁匆膊贿x,也能滿?體積不?于 j 的情況,此時(shí)的價(jià)值為 0 。
4. 填表順序:
根據(jù)「狀態(tài)轉(zhuǎn)移?程」,我們僅需「從上往下」填表即可。
5. 返回值:
根據(jù)「狀態(tài)表?」,返回 dp[n][V] 。
接下來(lái)解決第?問(wèn):
第?問(wèn)僅需微調(diào)?下 dp 過(guò)程的五步即可。
因?yàn)橛锌赡軠惒? j 體積的物品,因此我們把不合法的狀態(tài)設(shè)置為 -1 。
1. 狀態(tài)表?:
dp[i][j] 表?:從前 i 個(gè)物品中挑選,總體積「正好」等于 j ,所有的選法中,能挑選出來(lái)的最?價(jià)值。
2. 狀態(tài)轉(zhuǎn)移?程:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。 但是在使? dp[i - 1][j - v[i]] 的時(shí)候,不僅要判斷 j >= v[i] ,?要判斷 dp[i - 1][j - v[i]] 表?的情況是否存在,也就是 dp[i - 1][j - v[i]] != -1 。
3. 初始化:
我們多加??,?便我們的初始化:
i. 第?個(gè)格?為 0 ,因?yàn)檎媚軠?體積為 0 的背包;
ii. 但是第??后?的格?都是 -1 ,因?yàn)闆](méi)有物品,?法滿?體積?于 0 的情況。
4. 填表順序:
根據(jù)「狀態(tài)轉(zhuǎn)移?程」,我們僅需「從上往下」填表即可。
5. 返回值:
由于最后可能湊不成體積為 V 的情況,因此返回之前需要「特判」?下。
空間優(yōu)化:
背包問(wèn)題基本上都是利?「滾動(dòng)數(shù)組」來(lái)做空間上的優(yōu)化:
i. 利?「滾動(dòng)數(shù)組」優(yōu)化;
ii. 直接在「原始代碼」上修改。
在01背包問(wèn)題中,優(yōu)化的結(jié)果為:
i. 刪掉所有的橫坐標(biāo);
ii. 修改?下 j 的遍歷順序。

例題二
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
先將問(wèn)題轉(zhuǎn)化成我們「熟悉」的題型。如果數(shù)組能夠被分成兩個(gè)相同元素之和相同的?集,那么原數(shù)組必須有下??個(gè)性質(zhì):
i. 所有元素之和應(yīng)該是?個(gè)偶數(shù);
ii. 數(shù)組中最?的元素應(yīng)該?于所有元素總和的?半;
iii. 挑選?些數(shù),這些數(shù)的總和應(yīng)該等于數(shù)組總和的?半。
根據(jù)前兩個(gè)性質(zhì),我們可以提前判斷數(shù)組能夠被劃分。根據(jù)最后?個(gè)性質(zhì),我們發(fā)現(xiàn)問(wèn)題就轉(zhuǎn)化成
了「01 背包」的模型:
i. 數(shù)組中的元素只能選擇?次;
ii. 每個(gè)元素?臨被選擇或者不被選擇的處境;
iii. 選出來(lái)的元素總和要等于所有元素總和的?半。
其中,數(shù)組內(nèi)的元素就是物品,總和就是背包。那么我們就可以?背包模型的分析?式,來(lái)處理這道題。 請(qǐng)?家注意,「不要背」?fàn)顟B(tài)轉(zhuǎn)移?程,因?yàn)轭}型變化之后,狀態(tài)轉(zhuǎn)移?程就會(huì)跟著變化。我們要記住的是分析問(wèn)題的模式。?這種分析問(wèn)題的模式來(lái)解決問(wèn)題。
1. 狀態(tài)表?:
dp[i][j] 表?在前 i 個(gè)元素中選擇,所有的選法中,能否湊成總和為 j 這個(gè)數(shù)。
2. 狀態(tài)轉(zhuǎn)移?程:
?規(guī)矩,根據(jù)「最后?個(gè)位置」的元素,結(jié)合題?的要求,分情況討論:
i. 不選擇 nums[i] :那么我們是否能夠湊成總和為 j ,就要看在前 i - 1 個(gè)元素中選,能否湊成總和為 j 。根據(jù)狀態(tài)表?,此時(shí) dp[i][j] = dp[i - 1][j] ;
ii. 選擇 nums[i] :這種情況下是有前提條件的,此時(shí)的 nums[i] 應(yīng)該是?于等于 j 。
因?yàn)槿绻@個(gè)元素都?要湊成的總和?,選擇它就沒(méi)有意義呀。那么我們是否能夠湊成總和為 j ,就要看在前 i - 1 個(gè)元素中選,能否湊成總和為 j - nums[i] 。根據(jù)狀態(tài)表?,此時(shí) dp[i][j] = dp[i - 1][j - nums[i]] 。
綜上所述,兩種情況下只要有?種能夠湊成總和為 j ,那么這個(gè)狀態(tài)就是 true 。因此,狀態(tài)轉(zhuǎn)移?程為: dp[i][j] = dp[i - 1][j]
if(nums[i - 1] <= j) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i-1]]
3. 初始化:
由于需要?到上??的數(shù)據(jù),因此我們可以先把第??初始化。第??表?不選擇任何元素,要湊成?標(biāo)和 j 。只有當(dāng)?標(biāo)和為 0 的時(shí)候才能做到,因此第??僅需初始化第?個(gè)元素 dp[0][0] = true
4. 填表順序:
根據(jù)「狀態(tài)轉(zhuǎn)移?程」,我們需要「從上往下」填寫每??,每??的順序是「?所謂的」。
5. 返回值: ?
根據(jù)「狀態(tài)表?」,返回 dp[n][aim] 的值。其中 n 表?數(shù)組的??, aim 表?要湊的?標(biāo)和。

6. 空間優(yōu)化:
所有的「背包問(wèn)題」,都可以進(jìn)?空間上的優(yōu)化。
對(duì)于 01背包類型的,我們的優(yōu)化策略是:
i. 刪掉第?維;
ii. 修改第?層循環(huán)的遍歷順序即可。

例題三
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
本題可以直接?「暴搜」的?法解決。但是稍微?數(shù)學(xué)知識(shí)分析?下,就能轉(zhuǎn)化成我們常?的「背
包模型」的問(wèn)題。設(shè)我們最終選取的結(jié)果中,前?加 + 號(hào)的數(shù)字之和為 a ,前?加 - 號(hào)的數(shù)字之和為 b ,整個(gè)數(shù)組的總和為 sum ,于是我們有:
? a + b = sum
? a - b = target
上?兩個(gè)式?消去 b 之后,可以得到 a = (sum + target) / 2,也就是說(shuō),我們僅需在 nums 數(shù)組中選擇?些數(shù),將它們湊成和為 (sum + target) / 2 即可。問(wèn)題就變成了 416. 分割等和?集 這道題。
我們可以?相同的分析模式,來(lái)處理這道題。
1. 狀態(tài)表?:
dp[i][j] 表?:在前 i 個(gè)數(shù)中選,總和正好等于 j ,?共有多少種選法。
2. 狀態(tài)轉(zhuǎn)移?程:
?規(guī)矩,根據(jù)「最后?個(gè)位置」的元素,結(jié)合題?的要求,我們有「選擇」最后?個(gè)元素或者「不
選擇」最后?個(gè)元素兩種策略:
i. 不選 nums[i] :那么我們湊成總和 j 的總?案,就要看在前 i - 1 個(gè)元素中選,湊成總和為 j 的?案數(shù)。根據(jù)狀態(tài)表?,此時(shí) dp[i][j] = dp[i - 1][j] ;
ii. 選擇 nums[i] :這種情況下是有前提條件的,此時(shí)的 nums[i] 應(yīng)該是?于等于 j 。
因?yàn)槿绻@個(gè)元素都?要湊成的總和?,選擇它就沒(méi)有意義呀。那么我們能夠湊成總和為 j 的?案數(shù),就要看在前 i - 1 個(gè)元素中選,能否湊成總和為 j - nums[i] 。根據(jù)狀態(tài)表?,此時(shí) dp[i][j] = dp[i - 1][j - nums[i]]
綜上所述,兩種情況如果存在的話,應(yīng)該要累加在?起。因此,狀態(tài)轉(zhuǎn)移?程為:
dp[i][j] = dp[i - 1][j]
if(nums[i - 1] <= j) dp[i][j] = dp[i][j] += dp[i - 1][j - nums[i - 1]]
3. 初始化:
由于需要?到「上??」的數(shù)據(jù),因此我們可以先把第??初始化。第??表?不選擇任何元素,要湊成?標(biāo)和 j 。只有當(dāng)?標(biāo)和為 0 的時(shí)候才能做到,因此第??僅需初始化第?個(gè)元素 dp[0][0] = 1
4. 填表順序:
根據(jù)「狀態(tài)轉(zhuǎn)移?程」,我們需要「從上往下」填寫每??,每??的順序是「?所謂的」。
5. 返回值:
根據(jù)「狀態(tài)表?」,返回 dp[n][aim] 的值。其中 n 表?數(shù)組的??, aim 表?要湊的?標(biāo)和。

6. 空間優(yōu)化:
所有的「背包問(wèn)題」,都可以進(jìn)?空間上的優(yōu)化。
對(duì)于 01背包類型的,我們的優(yōu)化策略是:
i. 刪掉第?維;
ii. 修改第?層循環(huán)的遍歷順序即可。

例題四
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
先將問(wèn)題「轉(zhuǎn)化」成我們熟悉的題型。
? 任意兩塊?頭在?起粉碎,重量相同的部分會(huì)被丟掉,重量有差異的部分會(huì)被留下來(lái)。那就相當(dāng)于在原始的數(shù)據(jù)的前?,加上「加號(hào)」或者「減號(hào)」,是最終的結(jié)果最?即可。也就是說(shuō)把原始的?頭分成兩部分,兩部分的和越接近越好。
? ?因?yàn)楫?dāng)所有元素的和固定時(shí),分成的兩部分越接近數(shù)組「總和的?半」,兩者的差越?。
因此問(wèn)題就變成了:在數(shù)組中選擇?些數(shù),讓這些數(shù)的和盡量接近 sum / 2 ,如果把數(shù)看成物品,每個(gè)數(shù)的值看成體積和價(jià)值,問(wèn)題就變成了「01 背包問(wèn)題」。
1. 狀態(tài)表?:
dp[i][j] 表?在前 i 個(gè)元素中選擇,總和不超過(guò) j,此時(shí)所有元素的「最?和」。
2. 狀態(tài)轉(zhuǎn)移?程:
?規(guī)矩,根據(jù)「最后?個(gè)位置」的元素,結(jié)合題?的要求,分情況討論:
i. 不選 stones[i] :那么我們是否能夠湊成總和為 j ,就要看在前 i - 1 個(gè)元素中選,能否湊成總和為 j 。根據(jù)狀態(tài)表?,此時(shí) dp[i][j] = dp[i - 1][j] ;
ii. 選擇 stones[i] :這種情況下是有前提條件的,此時(shí)的 stones[i] 應(yīng)該是?于等于 j 。因?yàn)槿绻@個(gè)元素都?要湊成的總和?,選擇它就沒(méi)有意義呀。那么我們是否能夠湊成總和為 j ,就要看在前 i - 1 個(gè)元素中選,能否湊成總和為 j - stones[i] 。根據(jù)狀態(tài)表?,此時(shí) dp[i][j] = dp[i - 1][j -stones[i]] + stones[i] 。
綜上所述,我們要的是最?價(jià)值。因此,狀態(tài)轉(zhuǎn)移?程為:
dp[i][j] = dp[i - 1][j]
if(j >= stones[i]) dp[i][j] = max(dp[i][j] ,?dp[i - 1][j - stones[i]] + stones[i]) 。
3. 初始化:
由于需要?到上??的數(shù)據(jù),因此我們可以先把第??初始化。第??表?「沒(méi)有??」。因此想湊成?標(biāo)和 j ,最?和都是 0 。
4. 填表順序:
根據(jù)「狀態(tài)轉(zhuǎn)移?程」,我們需要「從上往下」填寫每??,每??的順序是「?所謂的」。
5. 返回值:
a. 根據(jù)「狀態(tài)表?」,先找到最接近 sum / 2 的最?和 dp[n][sum / 2] ;
b. 因?yàn)槲覀円氖莾啥??的差,因此返回 sum - 2 * dp[n][sum / 2] 。

6. 空間優(yōu)化:
所有的背包問(wèn)題,都可以進(jìn)?「空間」上的優(yōu)化。
對(duì)于 01背包類型的,我們的優(yōu)化策略是:
i. 刪掉第?維;
ii. 修改第?層循環(huán)的「遍歷順序」即可。

完全背包問(wèn)題
例題一
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
背包問(wèn)題的狀態(tài)表??常經(jīng)典,如果?家不知道怎么來(lái)的,就把它當(dāng)成?個(gè)模板記住吧~
我們先解決第?問(wèn):
1. 狀態(tài)表?:
dp[i][j] 表?:從前 i 個(gè)物品中挑選,總體積不超過(guò) j ,所有的選法中,能挑選出來(lái)的最?價(jià)值.(這?是和 01背包?樣噠)
2. 狀態(tài)轉(zhuǎn)移?程:
線性 dp 狀態(tài)轉(zhuǎn)移?程分析?式,?般都是根據(jù)最后?步的狀況,來(lái)分情況討論。但是最后?個(gè)物品能選很多個(gè),因此我們的需要分很多情況:
i. 選 0 個(gè)第 i 個(gè)物品:此時(shí)相當(dāng)于就是去前 i - 1 個(gè)物品中挑選,總體積不超過(guò) j 。此時(shí)最?價(jià)值為 dp[i - 1][j] ;
ii. 選 1 個(gè)第 i 個(gè)物品:此時(shí)相當(dāng)于就是去前 i - 1 個(gè)物品中挑選,總體積不超過(guò) j - v[i] 。因?yàn)樘暨x了?個(gè) i 物品,此時(shí)最?價(jià)值為 dp[i - 1][j - v[i]] + w[i] ;
iii. 選 2 個(gè)第 i 個(gè)物品:此時(shí)相當(dāng)于就是去前 i - 1 個(gè)物品中挑選,總體積不超過(guò) j - 2 * v[i] 。因?yàn)樘暨x了兩個(gè) i 物品,此時(shí)最?價(jià)值為 dp[i - 1][j - 2 * v[i]] + 2 * w[i] ;
iv. ......
綜上,我們的狀態(tài)轉(zhuǎn)移?程為:
dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i], dp[i-1][j- 2*v[i]]+2*w[i]...)
當(dāng)我們發(fā)現(xiàn),計(jì)算?個(gè)狀態(tài)的時(shí)候,需要?個(gè)循環(huán)才能搞定的時(shí)候,我們要想到去優(yōu)化。優(yōu)化的?
向就是??個(gè)或者兩個(gè)狀態(tài)來(lái)表?這?堆的狀態(tài),通常就是?數(shù)學(xué)的?式做?下等價(jià)替換。我們發(fā)
現(xiàn)第?維是有規(guī)律的變化的,因此我們?nèi)タ纯? dp[i][j - v[i]] 這個(gè)狀態(tài):
dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2*v[i]]+w[i],dp[i-1] [j-3*v[i]]+2*w[i]...)
我們發(fā)現(xiàn),把 dp[i][j - v[i]] 加上 w[i] 正好和 dp[i][j] 中除了第?項(xiàng)以外的全部?致,因此我們可以修改我們的狀態(tài)轉(zhuǎn)移?程為: dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]) 。
3. 初始化:
我們多加??,?便我們的初始化,此時(shí)僅需將第??初始化為 0 即可。因?yàn)槭裁匆膊贿x,也能 滿?體積不?于 j 的情況,此時(shí)的價(jià)值為 0 。
4. 填表順序:
根據(jù)狀態(tài)轉(zhuǎn)移?程,我們僅需從上往下填表即可。
5. 返回值:
根據(jù)狀態(tài)表?,返回 dp[n][V] 。
接下來(lái)解決第?問(wèn):
第?問(wèn)僅需微調(diào)?下 dp 過(guò)程的五步即可。因?yàn)橛锌赡軠惒? j 體積的物品,因此我們把不合法的狀態(tài)設(shè)置為 -1 。
1. 狀態(tài)表?:
dp[i][j] 表?:從前 i 個(gè)物品中挑選,總體積正好等于 j ,所有的選法中,能挑選出來(lái)的最?價(jià)值。
2. 狀態(tài)轉(zhuǎn)移?程:
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]) 。
但是在使? dp[i][j - v[i]] 的時(shí)候,不僅要判斷 j >= v[i] ,?要判斷 dp[i][j - v[i]] 表?的情況是否存在,也就是 dp[i][j - v[i]] != -1 。
3. 初始化:
我們多加??,?便我們的初始化:
i. 第?個(gè)格?為 0 ,因?yàn)檎媚軠?體積為 0 的背包;
ii. 但是第??后?的格?都是 -1 ,因?yàn)闆](méi)有物品,?法滿?體積?于 0 的情況。
4. 填表順序:
根據(jù)狀態(tài)轉(zhuǎn)移?程,我們僅需從上往下填表即可。
5. 返回值:
由于最后可能湊不成體積為 V 的情況,因此返回之前需要特判?下。

空間優(yōu)化:
背包問(wèn)題基本上都是利?滾動(dòng)數(shù)組來(lái)做空間上的優(yōu)化:
i. 利?滾動(dòng)數(shù)組優(yōu)化;
ii. 直接在原始代碼上修改。
在完全背包問(wèn)題中,優(yōu)化的結(jié)果為:
i. 僅需刪掉所有的橫坐標(biāo)。

例題二
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
先將問(wèn)題「轉(zhuǎn)化」成我們熟悉的題型。
i. 在?些物品中「挑選」?些出來(lái),然后在滿?某個(gè)「限定條件」下,解決?些問(wèn)題,?概率是「背包」模型;
ii. 由于每?個(gè)物品都是?限多個(gè)的,因此是?個(gè)「完全背包」問(wèn)題。
接下來(lái)的分析就是基于「完全背包」的?式來(lái)的。
1. 狀態(tài)表?:
dp[i][j] 表?:從前 i 個(gè)硬幣中挑選,總和正好等于 j ,所有的選法中,最少的硬幣個(gè)數(shù)。
2. 狀態(tài)轉(zhuǎn)移?程:
線性 dp 狀態(tài)轉(zhuǎn)移?程分析?式,?般都是根據(jù)「最后?步」的狀況,來(lái)分情況討論。但是最后?個(gè)物品能選很多個(gè),因此我們的需要分很多情況:
i. 選 0 個(gè)第 i 個(gè)硬幣:此時(shí)相當(dāng)于就是去前 i - 1 個(gè)硬幣中挑選,總和正好等于 j 。此時(shí)最少的硬幣個(gè)數(shù)為 dp[i - 1][j] ;
ii. 選 1 個(gè)第 i 個(gè)硬幣:此時(shí)相當(dāng)于就是去前 i - 1 個(gè)硬幣中挑選,總和正好等于 j - v[i] 。因?yàn)樘暨x了?個(gè) i 硬幣,此時(shí)最少的硬幣個(gè)數(shù)為 dp[i - 1][j - coins[i]] + 1 ;
iii. 選 2 個(gè)第 i 個(gè)硬幣:此時(shí)相當(dāng)于就是去前 i - 1 個(gè)硬幣中挑選,總和正好等于 j - 2 * coins 。因?yàn)樘暨x了兩個(gè) i 硬幣,此時(shí)最少的硬幣個(gè)數(shù)為 dp[i - 1][j - 2 * coins[i]] + 2 ;
iv. ......
結(jié)合我們?cè)谕耆嘲??的優(yōu)化思路,我們最終得到的狀態(tài)轉(zhuǎn)移?程為:
dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1) 。
這?教給?家?個(gè)技巧,就是相當(dāng)于把第?種情況 dp[i - 1][j - coins[i]] + 1 ??的 i - 1 變成 i 即可。
3. 初始化:
初始化第??即可。這?因?yàn)槿?min ,所以我們可以把?效的地?設(shè)置成?窮? (0x3f3f3f3f)
因?yàn)檫@?要求正好湊成總和為 j ,因此,需要把第??除了第?個(gè)位置的元素,都設(shè)置成?窮?。
4. 填表順序:
根據(jù)「狀態(tài)轉(zhuǎn)移?程」,我們僅需「從上往下」填表即可。
5. 返回值:
根據(jù)「狀態(tài)表?」,返回 dp[n][V] 。但是要特判?下,因?yàn)橛锌赡軠惒坏健?/span>

空間優(yōu)化后的算法代碼:
例題三
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
先將問(wèn)題「轉(zhuǎn)化」成我們熟悉的題型。
i. 在?些物品中「挑選」?些出來(lái),然后在滿?某個(gè)「限定條件」下,解決?些問(wèn)題,?概率是背包模型;
ii. 由于每?個(gè)物品都是?限多個(gè)的,因此是?個(gè)「完全背包」問(wèn)題。接下來(lái)的分析就是基于「完全背包」的?式來(lái)的。
1. 狀態(tài)表?:
dp[i][j] 表?:從前 i 個(gè)硬幣中挑選,總和正好等于 j ,?共有多少種選法。
2. 狀態(tài)轉(zhuǎn)移?程:
線性 dp 狀態(tài)轉(zhuǎn)移?程分析?式,?般都是「根據(jù)最后?步」的狀況,來(lái)分情況討論。但是最后?個(gè)物品能選很多個(gè),因此我們的需要分很多情況:
i. 選 0 個(gè)第 i 個(gè)硬幣:此時(shí)相當(dāng)于就是去前 i - 1 個(gè)硬幣中挑選,總和正好等于 j 。此時(shí)選法個(gè)數(shù)為 dp[i - 1][j] ;
ii. 選 1 個(gè)第 i 個(gè)硬幣:此時(shí)相當(dāng)于就是去前 i - 1 個(gè)硬幣中挑選,總和正好等于 j - v[i] 。因?yàn)樘暨x了?個(gè) i 硬幣,此時(shí)選法個(gè)數(shù)為 dp[i - 1][j - coins[i]] ;
iii. 選 2 個(gè)第 i 個(gè)硬幣:此時(shí)相當(dāng)于就是去前 i - 1 個(gè)硬幣中挑選,總和正好等于 j - 2 * coins 。因?yàn)樘暨x了兩個(gè) i 硬幣,此時(shí)選法個(gè)數(shù)為 dp[i - 1][j - 2 * coins[i]] ;
iv. ......
結(jié)合我們?cè)谕耆嘲??的「優(yōu)化思路」,我們最終得到的狀態(tài)轉(zhuǎn)移?程為:
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]] 。
3. 初始化:
初始化第??即可。
第??表?沒(méi)有物品,沒(méi)有物品正好能湊能和為 0 的情況。因此 dp[0][0] = 1 ,其余位置都是 0 種情況。
4. 填表順序:
根據(jù)「狀態(tài)轉(zhuǎn)移?程」,我們僅需「從上往下」填表即可。
5. 返回值:
根據(jù)「狀態(tài)表?」,返回 dp[n][V] 。

空間優(yōu)化后的算法代碼:

例題四
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
這?給出?個(gè)?「拆分出相同?問(wèn)題」的?式,定義?個(gè)狀態(tài)表?。(?「完全背包」?式的解法
就仿照之前的分析模式就好啦~~)為了敘述?便,把和為 n 的完全平?數(shù)的最少數(shù)量簡(jiǎn)稱為「最?數(shù)量」。對(duì)于 12 這個(gè)數(shù),我們分析?下如何求它的最?數(shù)量。
? 如果 12 本?就是完全平?數(shù),我們不?算了,直接返回 1 ;
? 但是 12 不是完全平?數(shù),我們?cè)囍褑?wèn)題分解?下:
1. 情況?:拆出來(lái)?個(gè) 1 ,然后看看 11 的最?數(shù)量,記為 x1 ;
2. 情況?:拆出來(lái)?個(gè) 4 ,然后看看 8 的最?數(shù)量,記為 x2 ;(為什么拆出來(lái) 4 ,?不拆出來(lái) 2 呢?)
3. 情況三:拆出來(lái)?個(gè) 8 ......
其中,我們接下來(lái)求 11 、 8 的時(shí)候,其實(shí)?回到了原來(lái)的問(wèn)題上。因此,我們可以嘗試? dp 的策略,將 1 2 3 4 6 等等這些數(shù)的最?數(shù)量依次保存起來(lái)。再求較?的 n 的時(shí)候,直接查表,然后找出最?數(shù)量。
1. 狀態(tài)表?:
dp[i] 表?:和為 i 的完全平?數(shù)的最少數(shù)量。
2. 狀態(tài)轉(zhuǎn)移?程:
對(duì)于 dp[i] ,根據(jù)思路那?的分析我們知道,可以根據(jù)?于等于 i 的所有完全平?數(shù) x 進(jìn)?劃分:
? x = 1 時(shí),最?數(shù)量為: 1 + dp[i - 1] ;
? x = 4 時(shí),最?數(shù)量為: 1 + dp[i - 4] ......
?直枚舉到 x <= i 為?。
為了?便枚舉完全平?數(shù),我們采?下?的策略: for(int j = 1; j * j <= i; j++)
綜上所述,狀態(tài)轉(zhuǎn)移?程為: dp[i] = min(dp[i], dp[i - j * j] + 1)
3. 初始化:
當(dāng) n = 0 的時(shí)候,沒(méi)法拆分,結(jié)果為 0 ; 當(dāng) n = 1 的時(shí)候,顯然為 1 。
4. 填表順序:
從左往右。
5. 返回值:
根據(jù)題意,返回 dp[n] 的值。

空間優(yōu)化后的算法代碼:

?維費(fèi)?的背包問(wèn)題
例題一
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
先將問(wèn)題轉(zhuǎn)化成我們熟悉的題型。
i. 在?些物品中「挑選」?些出來(lái),然后在滿?某個(gè)「限定條件」下,解決?些問(wèn)題,?概率是背包模型;
ii. 由于每?個(gè)物品都只有 1 個(gè),因此是?個(gè)「01 背包問(wèn)題」。
但是,我們發(fā)現(xiàn)這?道題??有「兩個(gè)限制條件」。因此是?個(gè)「?維費(fèi)?的 01 背包問(wèn)題」。那
么我們定義狀態(tài)表?的時(shí)候,來(lái)?個(gè)三維 dp 表,把第?個(gè)限制條件加上即可。
1. 狀態(tài)表?:
dp[i][j][k] 表?:從前 i 個(gè)字符串中挑選,字符 0 的個(gè)數(shù)不超過(guò) j ,字符 1 的個(gè)數(shù)不超過(guò) k ,所有的選法中,最?的?度。
2. 狀態(tài)轉(zhuǎn)移?程:
線性 dp 狀態(tài)轉(zhuǎn)移?程分析?式,?般都是「根據(jù)最后?步」的狀況,來(lái)分情況討論。為了?便敘述,我們記第 i 個(gè)字符中,字符 0 的個(gè)數(shù)為 a ,字符 1 的個(gè)數(shù)為 b :
i. 不選第 i 個(gè)字符串:相當(dāng)于就是去前 i - 1 個(gè)字符串中挑選,并且字符 0 的個(gè)數(shù)不超過(guò) j ,字符 1 的個(gè)數(shù)不超過(guò) k 。此時(shí)的最??度為 dp[i][j][k] = dp[i - 1] [j][k] ;
ii. 選擇第 i 個(gè)字符串:那么接下來(lái)我僅需在前 i - 1 個(gè)字符串??,挑選出來(lái)字符 0 的個(gè)數(shù)不超過(guò) j - a ,字符 1 的個(gè)數(shù)不超過(guò) k - b 的最??度,然后在這個(gè)?度后?加上字符串 i 即可。此時(shí) dp[i][j][k] = dp[i - 1][j - a][k - b] + 1 。 但是這種狀態(tài)不?定存在,因此需要特判?下。
綜上,狀態(tài)轉(zhuǎn)移?程為: dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a] [k - b] + 1) 。
3. 初始化:
當(dāng)沒(méi)有字符串的時(shí)候,沒(méi)有?度,因此初始化為 0 即可。
4. 填表順序:
保證第?維的循環(huán)「從?到?」即可。
5. 返回值:
根據(jù)「狀態(tài)表?」,我們返回 dp[len][m][n] 。 其中 len 表?字符串?dāng)?shù)組的?度。

6. 空間優(yōu)化:
所有的「背包問(wèn)題」,都可以進(jìn)?空間上的優(yōu)化。
對(duì)于「?維費(fèi)?的 01 背包」類型的,我們的優(yōu)化策略是:
i. 刪掉第?維;
ii. 修改第?層以及第三層循環(huán)的遍歷順序即可。

例題二
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
這道題??常難讀懂,但是如果結(jié)合例?多讀?遍,你就會(huì)發(fā)現(xiàn)是?個(gè)經(jīng)典的「?維費(fèi)?的背包問(wèn) 題」。因此我們可以仿照「?維費(fèi)?的背包」來(lái)定義狀態(tài)表?。
1. 狀態(tài)表?:
dp[i][j][k] 表?:從前 i 個(gè)計(jì)劃中挑選,總?數(shù)不超過(guò) j ,總利潤(rùn)?少為 k ,?共有多少種選法。
注意注意注意,這道題??出現(xiàn)了?個(gè)「?少」,和我們之前做過(guò)的背包問(wèn)題不?樣。因此,我們 在分析「狀態(tài)轉(zhuǎn)移?程」的時(shí)候要結(jié)合實(shí)際情況考慮?下。
2. 狀態(tài)轉(zhuǎn)移?程:
?規(guī)矩,根據(jù)「最后?個(gè)位置」的元素,結(jié)合題?的要求,我們有「選擇」最后?個(gè)元素或者「不
選擇」最后?個(gè)元素兩種策略:
i. 不選 i 位置的計(jì)劃:那我們只能去前 i - 1 個(gè)計(jì)劃中挑選,總?數(shù)不超過(guò) j ,總利潤(rùn)?少為 k 。此時(shí)?共有 dp[i - 1][j][k] 種選法;
ii. 選擇 i 位置的計(jì)劃:那我們?cè)谇? i - 1 個(gè)計(jì)劃中挑選的時(shí)候,限制就變成了,總?數(shù)不超過(guò) j - g[i] ,總利潤(rùn)?少為 k - p[i] 。此時(shí)?共有 dp[i - 1][j - g[i]][k - p[i]] 。
第?種情況下有兩個(gè)細(xì)節(jié)需要注意:
1. j - g[i] < 0 :此時(shí)說(shuō)明 g[i] 過(guò)?,也就是?數(shù)過(guò)多。因?yàn)槲覀兊臓顟B(tài)表?要求?數(shù)是不能超過(guò) j 的,因此這個(gè)狀態(tài)是不合法的,需要舍去。
2. k - p[i] < 0 :此時(shí)說(shuō)明 p[i] 過(guò)?,也就是利潤(rùn)太?。但是利潤(rùn)?,不正是我們想要的嘛?所以這個(gè)狀態(tài)「不能舍去」。但是問(wèn)題來(lái)了,我們的 dp 表是沒(méi)有負(fù)數(shù)的下標(biāo)的,這就意味著這些狀態(tài)我們?法表?。其實(shí),根本不需要負(fù)的下標(biāo),我們根據(jù)實(shí)際情況來(lái)看,如果這個(gè)任務(wù)的利潤(rùn)已經(jīng)能夠達(dá)標(biāo)了,我們僅需在之前的任務(wù)中,挑選出來(lái)的利潤(rùn)?少為 0 就可以了。因?yàn)閷?shí)際情況不允許我們是負(fù)利潤(rùn),那么負(fù)利潤(rùn)就等價(jià)于利潤(rùn)?少為 0 的情況。所以說(shuō)這種情況就等價(jià)于 dp[i][j][0] ,我們可以對(duì) k - p[i] 的結(jié)果與 0 取?個(gè) max 。
綜上,我們的狀態(tài)轉(zhuǎn)移?程為: dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - g[i - 1]][max(0, k - p[i - 1])] 。
3. 初始化:
當(dāng)我們的利潤(rùn)為 0 的時(shí)候,我們的利潤(rùn)為 0 ,此時(shí)?論?數(shù)限制為多少,我們都能找到?個(gè)「空集」的 ?案。因此初始化 dp[i][j][0] 的位置為 1 ,其中0 <= i?<= m,0 <= j <= n 。
4. 填表順序:
根據(jù)「狀態(tài)轉(zhuǎn)移?程」,我們保證 i 從?到?即可。
5. 返回值:
根據(jù)「狀態(tài)表?」,我們返回 dp[len][m][n] 。
其中 len 表?字符串?dāng)?shù)組的?度。

6. 空間優(yōu)化:
所有的「背包問(wèn)題」,都可以進(jìn)?空間上的優(yōu)化。
對(duì)于「?維費(fèi)?的 01 背包」類型的,我們的優(yōu)化策略是:
i. 刪掉第?維;
ii. 修改第?層以及第三層循環(huán)的遍歷順序即可。

似包?包
例題一
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
?定要注意,我們的背包問(wèn)題本質(zhì)上求的是「組合」數(shù)問(wèn)題,?這?道題求的是「排列數(shù)」問(wèn)題。 因此我們不能被這道題給迷惑,還是?常規(guī)的 dp 思想來(lái)解決這道題。
1. 狀態(tài)表?:
這道題的狀態(tài)表?就是根據(jù)「拆分出相同?問(wèn)題」的?式,抽象出來(lái)?個(gè)狀態(tài)表?:當(dāng)我們?cè)谇?target 這個(gè)數(shù)?共有?種排列?式的時(shí)候,對(duì)于最后?個(gè)位置,如果我們拿出數(shù)組中的?個(gè)數(shù) x ,接下來(lái)就是去找 target - x ?共有多少種排列?式。因此我們可以抽象出來(lái)?個(gè)狀態(tài)表?:
dp[i] 表?:總和為 i 的時(shí)候,?共有多少種排列?案。
2. 狀態(tài)轉(zhuǎn)移?程:
對(duì)于 dp[i] ,我們根據(jù)「最后?個(gè)位置」劃分,我們可以選擇數(shù)組中的任意?個(gè)數(shù)nums[j] ,其中 0 <= j <= n - 1 。 當(dāng) nums[j] <= target 的時(shí)候,此時(shí)的排列數(shù)等于我們先找到 target - nums[j] 的?
案數(shù),然后在每?個(gè)?案后?加上?個(gè)數(shù)字 nums[j] 即可。因?yàn)橛泻芏鄠€(gè) j 符合情況,因此我們的狀態(tài)轉(zhuǎn)移?程為: dp[i] += dp[target - nums[j] ,其中 0 <= j <= n - 1 。
3. 初始化:
當(dāng)和為 0 的時(shí)候,我們可以什么都不選,「空集」?種?案,因此 dp[0] = 1 。
4. 填表順序:
根據(jù)「狀態(tài)轉(zhuǎn)移?程」易得「從左往右」。
5. 返回值:
根據(jù)「狀態(tài)表?」,我們要返回的是 dp[target] 的值。

卡特蘭數(shù)
例題一
解法(動(dòng)態(tài)規(guī)劃):
算法思路:
這道題屬于「卡特蘭數(shù)」的?個(gè)應(yīng)?,同樣能解決的問(wèn)題還有「合法的進(jìn)出棧序列」、「括號(hào)匹配
的括號(hào)序列」、「電影購(gòu)票」等等。如果感興趣的同學(xué)可以「百度」搜索卡特蘭數(shù),會(huì)有很多詳細(xì)
的介紹。
1. 狀態(tài)表?:
這道題的狀態(tài)表?就是根據(jù)「拆分出相同?問(wèn)題」的?式,抽象出來(lái)?個(gè)狀態(tài)表?:
當(dāng)我們?cè)谇髠€(gè)數(shù)為 n 的 BST 的個(gè)數(shù)的時(shí)候,當(dāng)確定?個(gè)根節(jié)點(diǎn)之后,左右?樹的結(jié)點(diǎn)「?jìng)€(gè)數(shù)」也確定了。此時(shí)左右?樹就會(huì)變成相同的?問(wèn)題,因此我們可以這樣定義狀態(tài)表?:dp[i] 表?:當(dāng)結(jié)點(diǎn)的數(shù)量為 i 個(gè)的時(shí)候,?共有多少顆 BST 。難的是如何推導(dǎo)狀態(tài)轉(zhuǎn)移?程,因?yàn)樗覀冎俺?的狀態(tài)轉(zhuǎn)移?程不是很像。
2. 狀態(tài)轉(zhuǎn)移?程:
對(duì)于 dp[i] ,此時(shí)我們已經(jīng)有 i 個(gè)結(jié)點(diǎn)了,為了?便敘述,我們將這 i 個(gè)結(jié)點(diǎn)排好序,并且編上 1, 2, 3, 4, 5.....i 的編號(hào)。那么,對(duì)于所有不同的 BST ,我們可以按照下?的劃分規(guī)則,分成不同的 i 類:「按照不同的頭結(jié)點(diǎn)來(lái)分類」。分類結(jié)果就是:
i. 頭結(jié)點(diǎn)為 1 號(hào)結(jié)點(diǎn)的所有 BST
ii. 頭結(jié)點(diǎn)為 2 號(hào)結(jié)點(diǎn)的所有 BST
iii. ......
如果我們能求出「每?類中的 BST 的數(shù)量」,將所有類的 BST 數(shù)量累加在?起,就是最后結(jié)果。 接下來(lái)選擇「頭結(jié)點(diǎn)為 j 號(hào)」的結(jié)點(diǎn),來(lái)分析這 i 類 BST 的通?求法。如果選擇「 j 號(hào)結(jié)點(diǎn)來(lái)作為頭結(jié)點(diǎn)」,根據(jù) BST 的定義:
i. j 號(hào)結(jié)點(diǎn)的「左?樹」的結(jié)點(diǎn)編號(hào)應(yīng)該在 [1, j - 1] 之間,?共有 j - 1 個(gè)結(jié)點(diǎn)。那么 j 號(hào)結(jié)點(diǎn)作為頭結(jié)點(diǎn)的話,它的「左?樹的種類」就有 dp[j - 1] 種(回顧?下我們 dp 數(shù)組的定義哈);
ii. j 號(hào)結(jié)點(diǎn)的「右?樹」的結(jié)點(diǎn)編號(hào)應(yīng)該在 [j + 1, i] 之間,?共有 i - j 個(gè)結(jié)點(diǎn)。那么 j 號(hào)結(jié)點(diǎn)作為頭結(jié)點(diǎn)的話,它的「右?樹的種類」就有 dp[i - j] 種;根據(jù)「排列組合」的原理可得: j 號(hào)結(jié)點(diǎn)作為頭結(jié)點(diǎn)的 BST 的種類?共有 dp[j - 1] * dp[i - j] 種!因此,我們只要把「不同頭結(jié)點(diǎn)的 BST 數(shù)量」累加在?起,就能得到 dp[i] 的值: dp[i] += dp[j - 1] * dp[i - j] ( 1 <= j <= i) ?!缸⒁?的是 += ,并且 j 從 1 變化到 i 」。
3. 初始化:
我們注意到,每?個(gè)狀態(tài)轉(zhuǎn)移??的 j - 1 和 i - j 都是?于 i 的,并且可能會(huì)?到前?個(gè)的狀態(tài)(當(dāng) i = 1 , j = 1 的時(shí)候,要?到 dp[0] 的數(shù)據(jù))。因此要先把第?個(gè)元素初始化。當(dāng) i = 0 的時(shí)候,表??顆空樹,「空樹也是?顆?叉搜索樹」,因此 dp[0] = 1 。
4. 填表順序:
根據(jù)「狀態(tài)轉(zhuǎn)移?程」,易得「從左往右」。
5. 返回值:
根據(jù)「狀態(tài)表?」,我們要返回的是 dp[n] 的值。