動態(tài)規(guī)劃——回望過去

配套視頻：動態(tài)規(guī)劃——回望過去_嗶哩嗶哩_bilibili

主要思想：

? ? ? ? “那些忘記過去的人，注定要重蹈覆轍?！?/span>

? ? ? ? 比如說，一共有N個數(shù)，第一個數(shù)有一個值，第N個數(shù)也有一個值，問從第一個數(shù)到第N個數(shù)的累加和為多少。在這道題中，可以將數(shù)組狀態(tài)設為從1到當前數(shù)i的累加和，我們用Si來代表第i個狀態(tài)，那么Si = Si-1 + Ni就是狀態(tài)轉移的關系式。大體上來講就是設狀態(tài)，找關系。

? ? ? ?例子解釋的很清楚。正如例子所說，B記住了之前的答案“8”，當又多了一個“+1”時，B就直接可以將“8”+“1”。但如果B沒有記住之前的答案“8”，那么“B”就只能重新一個一個算了。像這種簡單的1+1問題還好，從頭算也花不了多長時間，但如果是很麻煩的問題，那記住過往就很重要了。

適用范圍：

? ? ? ? 動態(tài)規(guī)劃多用于求解最值（最優(yōu)、最大、最小、最長）問題；而且動態(tài)規(guī)劃解決的問題一般是可以分解的，適用于求“n的累加和”，“n的階乘”這類問題。

題目：

1.過河卒（馬攔過河卒）

2.最大字段和

總結：

? ? ? ?今天我們聊了聊【動態(tài)規(guī)劃】，它的主旨是將待求解的問題分解稱若干個子問題，并存儲子問題的解而避免計算重復的子問題，并由子問題的解得到原問題的解。

? ? ? ?動態(tài)規(guī)劃多用于求解最值（最優(yōu)、最大、最小、最長）問題；而且動態(tài)規(guī)劃解決的問題一般是可以分解的。

好啦，關于動態(tài)規(guī)劃就說到這里。這里是康郭聊算法，拜拜！

#注：例題答案請查看視頻。