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

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

背包問題

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

編輯距離問題

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