C++動(dòng)態(tài)規(guī)劃 小結(jié)

• 動(dòng)態(tài)規(guī)劃對(duì)問(wèn)題進(jìn)行分解，并通過(guò)存儲(chǔ)子問(wèn)題的解來(lái)規(guī)避重復(fù)計(jì)算，實(shí)現(xiàn)高效的計(jì)算效率。
• 不考慮時(shí)間的前提下，所有動(dòng)態(tài)規(guī)劃問(wèn)題都可以用回溯（暴力搜索）進(jìn)行求解，但遞歸樹(shù)中存在大量的重疊子問(wèn)題，效率極低。通過(guò)引入記憶化列表，可以存儲(chǔ)所有計(jì)算過(guò)的子問(wèn)題的解，從而保證重疊子問(wèn)題只被計(jì)算一次。
• 記憶化遞歸是一種從頂至底的遞歸式解法，而與之對(duì)應(yīng)的動(dòng)態(tài)規(guī)劃是一種從底至頂?shù)倪f推式解法，其如同“填寫(xiě)表格”一樣。由于當(dāng)前狀態(tài)僅依賴于某些局部狀態(tài)，因此我們可以消除 $dp$ 表的一個(gè)維度，從而降低空間復(fù)雜度。
• 子問(wèn)題分解是一種通用的算法思路，在分治、動(dòng)態(tài)規(guī)劃、回溯中具有不同的性質(zhì)。
• 動(dòng)態(tài)規(guī)劃問(wèn)題的三大特性：重疊子問(wèn)題、最優(yōu)子結(jié)構(gòu)、無(wú)后效性。
• 如果原問(wèn)題的最優(yōu)解可以從子問(wèn)題的最優(yōu)解構(gòu)建得來(lái)，則它就具有最優(yōu)子結(jié)構(gòu)。
• 無(wú)后效性指對(duì)于一個(gè)狀態(tài)，其未來(lái)發(fā)展只與該狀態(tài)有關(guān)，與其所經(jīng)歷的過(guò)去的所有狀態(tài)無(wú)關(guān)。許多組合優(yōu)化問(wèn)題都不具有無(wú)后效性，無(wú)法使用動(dòng)態(tài)規(guī)劃快速求解。

背包問(wèn)題

• 背包問(wèn)題是最典型的動(dòng)態(tài)規(guī)劃題目，具有 0-1 背包、完全背包、多重背包等變種問(wèn)題。
• 0-1 背包的狀態(tài)定義為前 $i$ 個(gè)物品在剩余容量為 $c$ 的背包中的最大價(jià)值。根據(jù)不放入背包和放入背包兩種決策，可得到最優(yōu)子結(jié)構(gòu)，并構(gòu)建出狀態(tài)轉(zhuǎn)移方程。在空間優(yōu)化中，由于每個(gè)狀態(tài)依賴正上方和左上方的狀態(tài)，因此需要倒序遍歷列表，避免左上方狀態(tài)被覆蓋。
• 完全背包的每種物品的選取數(shù)量無(wú)限制，因此選擇放入物品的狀態(tài)轉(zhuǎn)移與 0-1 背包不同。由于狀態(tài)依賴于正上方和正左方的狀態(tài)，因此在空間優(yōu)化中應(yīng)當(dāng)正序遍歷。
• 零錢兌換問(wèn)題是完全背包的一個(gè)變種。它從求“最大”價(jià)值變?yōu)榍蟆白钚　庇矌艛?shù)量，因此狀態(tài)轉(zhuǎn)移方程中的 $max()$ 應(yīng)改為 $min()$ 。從求“不超過(guò)”背包容量到求“恰好”湊出目標(biāo)金額，因此使用 $amt+1$ 來(lái)表示“無(wú)法湊出目標(biāo)金額”的無(wú)效解。
• 零錢兌換 II 問(wèn)題從求“最少硬幣數(shù)量”改為求“硬幣組合數(shù)量”，狀態(tài)轉(zhuǎn)移方程相應(yīng)地從 $min()$ 改為求和運(yùn)算符。

編輯距離問(wèn)題

• 編輯距離（Levenshtein 距離）用于衡量?jī)蓚€(gè)字符串之間的相似度，其定義為從一個(gè)字符串到另一個(gè)字符串的最小編輯步數(shù)，編輯操作包括添加、刪除、替換。
• 編輯距離問(wèn)題的狀態(tài)定義為將 $s$ 的前 $i$ 個(gè)字符更改為 $t$ 的前 $j$ 個(gè)字符所需的最少編輯步數(shù)。當(dāng) $s[i]\ne t[j]$ 時(shí)，具有三種決策：添加、刪除、替換，它們都有相應(yīng)的剩余子問(wèn)題。據(jù)此便可以找出最優(yōu)子結(jié)構(gòu)與構(gòu)建狀態(tài)轉(zhuǎn)移方程。而當(dāng) $s[i]=t[j]$ 時(shí)，無(wú)須編輯當(dāng)前字符。
• 在編輯距離中，狀態(tài)依賴于其正上方、正左方、左上方的狀態(tài)，因此空間優(yōu)化后正序或倒序遍歷都無(wú)法正確地進(jìn)行狀態(tài)轉(zhuǎn)移。為此，我們利用一個(gè)變量暫存左上方狀態(tài)，從而轉(zhuǎn)化到與完全背包等價(jià)的情況，可以在空間優(yōu)化后進(jìn)行正序遍歷。