一、動(dòng)態(tài)規(guī)劃基本原理
1. 理解動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃（Dynamic Programming, DP）是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的，通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的*。這些子問題之間通常是重疊的，即一個(gè)子問題的解可能會(huì)被多個(gè)子問題所使用。
2. 動(dòng)態(tài)規(guī)劃的三個(gè)特征
- *子結(jié)構(gòu)：原問題的*解包含其子問題的*解。
- 無后效性：即某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。
- 重復(fù)子問題：即子問題之間是不獨(dú)立的，一個(gè)子問題在下一階段決策中可能被多次使用到。
二、力扣上的動(dòng)態(tài)規(guī)劃解題思路
1. 定義子問題
將原問題分解成若干個(gè)規(guī)模較小的子問題，并定義這些子問題的解。子問題通常是參數(shù)化的，可以通過遞歸或迭代的方式求解。
2. 狀態(tài)轉(zhuǎn)移方程
找到子問題之間的遞推關(guān)系，即狀態(tài)轉(zhuǎn)移方程。這是動(dòng)態(tài)規(guī)劃解題的核心，通過狀態(tài)轉(zhuǎn)移方程可以計(jì)算出所有子問題的解，并最終得到原問題的解。
3. 初始化與邊界條件
在求解過程中，需要初始化一些基本的狀態(tài)，并處理好邊界條件。這些基本狀態(tài)和邊界條件是遞推計(jì)算的起點(diǎn)，必須保證正確無誤。
4. 遞推計(jì)算
根據(jù)狀態(tài)轉(zhuǎn)移方程，通過遞推或迭代的方式計(jì)算出所有子問題的解。在計(jì)算過程中，需要利用已經(jīng)計(jì)算出的子問題的解來求解當(dāng)前子問題的解。
5. 返回結(jié)果
當(dāng)所有子問題的解都計(jì)算完成后，就可以根據(jù)原問題的定義返回最終結(jié)果了。
三、力扣上的動(dòng)態(tài)規(guī)劃學(xué)習(xí)路徑
1. 基礎(chǔ)題目練習(xí)
初學(xué)者可以從力扣上的基礎(chǔ)動(dòng)態(tài)規(guī)劃題目開始練習(xí)，如斐波那契數(shù)列、爬樓梯等。這些題目相對簡單，但涵蓋了動(dòng)態(tài)規(guī)劃的基本概念和解題思路。
2. 進(jìn)階題目挑戰(zhàn)
在掌握了基礎(chǔ)動(dòng)態(tài)規(guī)劃題目后，可以挑戰(zhàn)一些進(jìn)階題目，如背包問題、打家劫舍、股票買賣等。這些題目需要更深入地理解動(dòng)態(tài)規(guī)劃的原理和技巧，并能夠靈活運(yùn)用狀態(tài)轉(zhuǎn)移方程進(jìn)行求解。
3. 深入理解與總結(jié)
在解題過程中，要注重對動(dòng)態(tài)規(guī)劃原理的深入理解和對解題技巧的總結(jié)?？梢酝ㄟ^閱讀相關(guān)書籍、博客和教程等方式加深對動(dòng)態(tài)規(guī)劃的理解，并學(xué)會(huì)將所學(xué)知識(shí)應(yīng)用到實(shí)際問題中去。
4. 實(shí)戰(zhàn)演練
*，要通過大量的實(shí)戰(zhàn)演練來鞏固所學(xué)知識(shí)并提高解題能力?？梢詤⒓恿凵系谋荣惢蛱魬?zhàn)賽來檢驗(yàn)自己的水平，并與其他選手交流學(xué)習(xí)心得和技巧。
四、示例題目分析
以力扣上的“打家劫舍”題目為例，該題目要求在一個(gè)由非負(fù)整數(shù)組成的數(shù)組中，你扮演一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的*制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的*金額。
解題思路：
- 定義子問題：f(k) 表示偷前 k 個(gè)房子能夠得到的*金額。
- 狀態(tài)轉(zhuǎn)移方程：f(k) = max(f(k-1), nums[k-1] + f(k-2))，其中 nums[k-1] 表示第 k 個(gè)房子的金額。
- 初始化與邊界條件：f(0) = 0（沒有房子可偷），f(1) = nums[0]（只有一個(gè)房子可偷）。
- 遞推計(jì)算：從 f(2) 開始遞推計(jì)算每個(gè) f(k) 的值，直到計(jì)算出 f(n)（n 為數(shù)組長度）。
- 返回結(jié)果：返回 f(n) 即為所求的*金額。
