從遞歸轉(zhuǎn)換到動(dòng)態(tài)規(guī)劃
如果一個(gè)遞歸函數(shù)有n個(gè)參數(shù)，那就定義一個(gè)n維數(shù)組，數(shù)組的下標(biāo)就是遞歸函數(shù)的取值范圍御蒲，數(shù)組元素的值是遞歸函數(shù)的返回值衣赶。
從邊界值開始，逐步填充數(shù)組厚满，就相當(dāng)于計(jì)算遞歸函數(shù)值的逆過程府瞄。
相當(dāng)于一個(gè)從下到上的過程
DP的一般思路
1、把原問題分解成若干個(gè)子問題——當(dāng)子問題全部解決的時(shí)候原問題即解決碘箍。子問題的解求出之后直接保存——每個(gè)子問題只求解一次遵馆。
2、確定狀態(tài)
一個(gè)“狀態(tài)”即為和子問題相關(guān)的各個(gè)變量的一組取值丰榴。一個(gè)“狀態(tài)”對(duì)應(yīng)于一個(gè)或者多個(gè)子問題货邓，所謂“某個(gè)狀態(tài)”的“值”，就是它所對(duì)應(yīng)的子問題的解四濒。
所有狀態(tài)的集合换况，構(gòu)成問題的“狀態(tài)空間”——狀態(tài)空間的大小與時(shí)間復(fù)雜度直接相關(guān)。對(duì)于數(shù)字三角形盗蟆，一共有N(N+1)/2個(gè)數(shù)字戈二，因此狀態(tài)空間一共有N(N+1)/2個(gè)狀態(tài)。
對(duì)于數(shù)字三角形：
子問題——第i行j列的數(shù)字到底邊的最大和
跟子問題相關(guān)的變量——i,j
狀態(tài)——i,j的一組取值姆涩，即為狀態(tài)對(duì)應(yīng)的子問題
狀態(tài)的值==子問題的解==(i,j)的最大和
有的時(shí)候K個(gè)整形變量構(gòu)成一個(gè)狀態(tài)挽拂，那么就用K維數(shù)組來存儲(chǔ)各個(gè)狀態(tài)的值——“值”可以是一個(gè)結(jié)構(gòu)體。一個(gè)狀態(tài)的值通常會(huì)是一個(gè)或者多個(gè)子問題的解骨饿。
3亏栈、確定一個(gè)初始狀態(tài)（邊界狀態(tài)）的值
初始狀態(tài)可以直接看出——對(duì)于數(shù)字三角形，初始狀態(tài)就是底邊數(shù)字宏赘，值即為底邊數(shù)字的值
4绒北、確定狀態(tài)轉(zhuǎn)移方程
找出不同狀態(tài)之間如何轉(zhuǎn)移——從一個(gè)已知狀態(tài)到一個(gè)未知狀態(tài)。即從一個(gè)或者多個(gè)“值”已知的狀態(tài)察署，求出另一個(gè)未知狀態(tài)的值——這個(gè)步驟可以用遞推公式表示闷游，即為狀態(tài)轉(zhuǎn)移方程
什么時(shí)候使用DP
1、問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)——即問題的最優(yōu)解所包含的子問題的解也是
最優(yōu)的
2贴汪、無后效性——當(dāng)前若干個(gè)狀態(tài)的值不受路徑影響脐往，只跟狀態(tài)有關(guān)
