定義
- 動(dòng)態(tài)規(guī)劃是屬于運(yùn)籌學(xué)的數(shù)學(xué)方法陈瘦，主要用于求解某類最優(yōu)化問題。一般情況下如果某個(gè)問題由多個(gè)交疊的子問題構(gòu)成痊项，并且子問題可由更小的子問題遞推得到時(shí)酥诽，就可以采用動(dòng)態(tài)規(guī)劃來求解鞍泉。求解動(dòng)態(tài)規(guī)劃問題最重要的就是找到遞推表達(dá)式肮帐。
算法案例：數(shù)組求最大和
-
已知一個(gè)整數(shù)數(shù)組 num=[1,5,3,7,9,3,4]，從數(shù)組中取出若干個(gè)數(shù)求和训枢，并且取出的數(shù)兩兩不相鄰，獲取其中最大的和恒界。動(dòng)態(tài)規(guī)劃可以簡單地理解為選或不選的問題。
以下題為例：
首先我們假設(shè)當(dāng)我們?nèi)〉降?i 個(gè)數(shù)時(shí)涩拙，最大和為 dp(i)
image.png
當(dāng) i 為 6 時(shí)耸采，此時(shí)有兩種情況兴泥，如果選擇第六個(gè)則和為前四個(gè)數(shù)最大和加上第六個(gè)數(shù)虾宇，如果不選為前五個(gè)數(shù)的最大和。以此類推下去便可以得到上圖，值完善了右邊的部分竭沫，由圖中可以看出左側(cè)部分和右側(cè)是有重復(fù)的骑篙，因此我們只需要將每次的計(jì)算結(jié)果保存在一個(gè)數(shù)組中便可以免去不必要的重復(fù)計(jì)算蜕提，因此可以得出以下的遞推公式
image.png
- PHP代碼實(shí)現(xiàn)
function rob($nums) {
$max = [$nums[0], max($nums[0], $nums[1])];
for ($i = 2; $i < count($nums); $i++)
{
$max[$i] = max(($nums[$i] + $max[$i - 2]), $max[$i - 1]);
}
return $max[count($nums) - 1];
}
特性
在用遞歸法自頂向下求解問題時(shí)谎势，每次產(chǎn)生的子問題并不總是新的子問題，有些子問題是反復(fù)被求解過的脏榆，因此我們將每次子問題的結(jié)果保存下來台谍，下次直接獲取其值须喂，不用再次計(jì)算趁蕊。
其他案例代碼
