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

背包問題

• 背包問題是最典型的動(dòng)態(tài)規(guī)劃題目，具有 0-1 背包、完全背包、多重背包等變種問題。
• 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ù)量無限制，因此選擇放入物品的狀態(tài)轉(zhuǎn)移與 0-1 背包不同。由于狀態(tài)依賴于正上方和正左方的狀態(tài)，因此在空間優(yōu)化中應(yīng)當(dāng)正序遍歷。
• 零錢兌換問題是完全背包的一個(gè)變種。它從求“最大”價(jià)值變?yōu)榍蟆白钚　庇矌艛?shù)量，因此狀態(tài)轉(zhuǎn)移方程中的 $max()$ 應(yīng)改為 $min()$ 。從求“不超過”背包容量到求“恰好”湊出目標(biāo)金額，因此使用 $amt+1$ 來表示“無法湊出目標(biāo)金額”的無效解。
• 零錢兌換 II 問題從求“最少硬幣數(shù)量”改為求“硬幣組合數(shù)量”，狀態(tài)轉(zhuǎn)移方程相應(yīng)地從 $min()$ 改為求和運(yùn)算符。

編輯距離問題

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