動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對(duì)解最優(yōu)化問(wèn)題的一種途徑车要、一種方法，最終問(wèn)題的最優(yōu)解可以通過(guò)前面子問(wèn)題的最優(yōu)解推導(dǎo)出來(lái)崭倘。
對(duì)于動(dòng)態(tài)規(guī)劃這個(gè)算法翼岁，自己學(xué)習(xí)的還不是很透徹，簡(jiǎn)單的總結(jié)自己學(xué)習(xí)的感受是：
1司光、動(dòng)態(tài)規(guī)劃思想中融合了遞歸和分治的思想琅坡，但不同于分治的是，動(dòng)態(tài)規(guī)劃求解中會(huì)通過(guò)狀態(tài)記錄求解過(guò)程中每一個(gè)分支的最優(yōu)解法残家，以此節(jié)省了許多重復(fù)計(jì)算榆俺。
2、動(dòng)態(tài)規(guī)劃最重要同樣也是最難的兩步是找到描述子問(wèn)題的狀態(tài)以及狀態(tài)間的推導(dǎo)關(guān)系坞淮。
3茴晋、比較可能使用動(dòng)態(tài)規(guī)劃的問(wèn)題：求最大最小值、是否有可行方案以及可行方案?jìng)€(gè)數(shù)回窘。
先來(lái)一個(gè)最常見(jiàn)的題體驗(yàn)一下诺擅，求斐波那契數(shù)列（1,1,2,3,5,8,13...）某個(gè)位置的值？
應(yīng)用分治法求解代碼
分治求解過(guò)程中毫玖，會(huì)有許多重復(fù)的運(yùn)算掀虎，如下圖3和2都被重復(fù)運(yùn)算了兩次，index值越大重復(fù)計(jì)算的次數(shù)就越多:
ok付枫，下面動(dòng)態(tài)規(guī)劃求解代碼:
我們定義了一個(gè)數(shù)組來(lái)記錄斐波那契每個(gè)位置的值烹玉，這就相當(dāng)于我們定義了一個(gè)狀態(tài)；每個(gè)位置的值等于它前面兩個(gè)的加和阐滩，這就相當(dāng)于一個(gè)狀態(tài)轉(zhuǎn)移方程二打。
這里通過(guò)數(shù)組記錄狀態(tài)就是一種以空間換時(shí)間的思想，其實(shí)和我們平時(shí)開(kāi)發(fā)用到的緩存的設(shè)計(jì)很像掂榔。
總結(jié)動(dòng)態(tài)規(guī)劃求解可以分為4步：
1继效、確定要解決的子問(wèn)題症杏，即狀態(tài)的定義。
2瑞信、列出狀態(tài)轉(zhuǎn)移方程厉颤。
3、根據(jù)給定條件凡简，初始化已知狀態(tài)值逼友。
4、求解最終問(wèn)題解秤涩。
下面再來(lái)解一道比較有意思的問(wèn)題帜乞，爬樓梯：
你正在爬樓梯，需要n步你才能到達(dá)頂部筐眷。但每次你只能爬一步或者兩步黎烈，你能有多少種不同的方法爬到樓頂部？
