一签孔、DP定義
動態(tài)規(guī)劃是一種將問題實例分解為更小的瑰艘、相似的子問題捶障，并存儲子問題的解而避免計算重復(fù)的子問題僧须，以解決最優(yōu)化問題的算法策略。
二项炼、區(qū)別
-
貪心處理的問題是：后一階段的最優(yōu)狀態(tài)依賴于前一階段的一個最優(yōu)狀態(tài)担平。
-
暴力搜索處理的問題是：后一階段的最優(yōu)狀態(tài)依賴于前一階段的多個狀態(tài)示绊，但和更之前的狀態(tài)沒關(guān)系；狀態(tài)沒重疊暂论。
三展哭、理解
解決DP問題的核心是找到最優(yōu)子結(jié)構(gòu)，這種結(jié)構(gòu)可以把次優(yōu)的路徑否決掉闻蛀，重疊狀態(tài)是否決掉這些次優(yōu)路徑的一個結(jié)果匪傍。
找到最優(yōu)子結(jié)構(gòu)->把次優(yōu)的路徑否決掉->重疊狀態(tài)保存->復(fù)雜度k^n變kn。
四觉痛、什么問題可以用DP役衡？
首先能狀態(tài)合并/有狀態(tài)轉(zhuǎn)移方程才行。每個問題的狀態(tài)轉(zhuǎn)移方程都不一樣薪棒。
如果問題本身沒有這種structure手蝎，則不能用動態(tài)規(guī)劃，也就是說不能否決掉一些路徑俐芯，那么只能暴力搜索了棵介。
五、應(yīng)用DP
- 建立狀態(tài)轉(zhuǎn)移方程
- 緩存并復(fù)用以往結(jié)果
- 按順序從小往大算：這里的“小”和“大”對應(yīng)的是問題的規(guī)模泼各，在這里也就是我們要從f(0)鞍时、f(1)、···到f(n)依次計算扣蜻。
參考：https://www.zhihu.com/question/39948290逆巍；
https://zhuanlan.zhihu.com/p/27033169；
