從遞歸轉(zhuǎn)換到動態(tài)規(guī)劃

如果一個遞歸函數(shù)有n個參數(shù)，那就定義一個n維數(shù)組，數(shù)組的下標就是遞歸函數(shù)的取值范圍，數(shù)組元素的值是遞歸函數(shù)的返回值。
從邊界值開始，逐步填充數(shù)組，就相當于計算遞歸函數(shù)值的逆過程。
相當于一個從下到上的過程

DP的一般思路

1、把原問題分解成若干個子問題——當子問題全部解決的時候原問題即解決。子問題的解求出之后直接保存——每個子問題只求解一次。
2、確定狀態(tài)
一個“狀態(tài)”即為和子問題相關的各個變量的一組取值。一個“狀態(tài)”對應于一個或者多個子問題，所謂“某個狀態(tài)”的“值”，就是它所對應的子問題的解。
所有狀態(tài)的集合，構成問題的“狀態(tài)空間”——狀態(tài)空間的大小與時間復雜度直接相關。對于數(shù)字三角形，一共有N(N+1)/2個數(shù)字，因此狀態(tài)空間一共有N(N+1)/2個狀態(tài)。
對于數(shù)字三角形：
子問題——第i行j列的數(shù)字到底邊的最大和
跟子問題相關的變量——i,j
狀態(tài)——i,j的一組取值，即為狀態(tài)對應的子問題
狀態(tài)的值==子問題的解==(i,j)的最大和

有的時候K個整形變量構成一個狀態(tài)，那么就用K維數(shù)組來存儲各個狀態(tài)的值——“值”可以是一個結(jié)構體。一個狀態(tài)的值通常會是一個或者多個子問題的解。

3、確定一個初始狀態(tài)（邊界狀態(tài)）的值
初始狀態(tài)可以直接看出——對于數(shù)字三角形，初始狀態(tài)就是底邊數(shù)字，值即為底邊數(shù)字的值

4、確定狀態(tài)轉(zhuǎn)移方程
找出不同狀態(tài)之間如何轉(zhuǎn)移——從一個已知狀態(tài)到一個未知狀態(tài)。即從一個或者多個“值”已知的狀態(tài)，求出另一個未知狀態(tài)的值——這個步驟可以用遞推公式表示，即為狀態(tài)轉(zhuǎn)移方程

什么時候使用DP

1、問題具有最優(yōu)子結(jié)構的性質(zhì)——即問題的最優(yōu)解所包含的子問題的解也是
最優(yōu)的
2、無后效性——當前若干個狀態(tài)的值不受路徑影響，只跟狀態(tài)有關