php算法學(xué)習(xí)之動(dòng)態(tài)規(guī)劃

　　動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對解最優(yōu)化問題的一種途徑、一種方法，最終問題的最優(yōu)解可以通過前面子問題的最優(yōu)解推導(dǎo)出來。下面小編為大家整理了php算法學(xué)習(xí)之動(dòng)態(tài)規(guī)劃，希望能幫到大家！

　　對于動(dòng)態(tài)規(guī)劃這個(gè)算法，自己學(xué)習(xí)的還不是很透徹，簡單的總結(jié)自己學(xué)習(xí)的感受是：

　　動(dòng)態(tài)規(guī)劃思想中融合了遞歸和分治的思想，但不同于分治的是，動(dòng)態(tài)規(guī)劃求解中會(huì)通過狀態(tài)記錄求解過程中每一個(gè)分支的最優(yōu)解法，以此節(jié)省了許多分支的重復(fù)計(jì)算。

　　動(dòng)態(tài)規(guī)劃最重要同樣也是最難的兩步是找到描述子問題的狀態(tài)以及狀態(tài)間的推導(dǎo)關(guān)系。

　　比較可能使用動(dòng)態(tài)規(guī)劃的問題：求最大最小值、是否有可行方案以及可行方案個(gè)數(shù)。

　　先來一個(gè)最常見的題體驗(yàn)一下，求斐波那契數(shù)列（不知道的同學(xué)請自行百度一下）某個(gè)位置的值？

　　應(yīng)用分治法求解代碼

　　分治求解過程中，會(huì)有許多重復(fù)的運(yùn)算，如下圖3和2都被重復(fù)運(yùn)算了兩次，index值越大重復(fù)計(jì)算的次數(shù)就越多。

　　ok，下面我們看一下動(dòng)態(tài)規(guī)劃如何進(jìn)行優(yōu)化。

　　我們定義了一個(gè)數(shù)組來記錄斐波那契每個(gè)位置的值，這就相當(dāng)于我們定義了一個(gè)狀態(tài)；每個(gè)位置的值等于它前面兩個(gè)的加和，這就相當(dāng)于一個(gè)狀態(tài)轉(zhuǎn)移方程。

　　這里通過數(shù)組記錄狀態(tài)就是一種以空間換時(shí)間的思想，其實(shí)和我們平時(shí)開發(fā)用到的緩存的設(shè)計(jì)很像。

　　總結(jié)動(dòng)態(tài)規(guī)劃求解可以分為4步：

　　1、確定要解決的子問題，即狀態(tài)的定義。

　　2、列出狀態(tài)轉(zhuǎn)移方程。

　　3、根據(jù)給定條件，初始化已知狀態(tài)值。

　　4、求解最終問題解。

　　下面再來解一道比較有意思的問題，爬樓梯：

　　你正在爬樓梯，需要n步你才能到達(dá)頂部。但每次你只能爬一步或者兩步，你能有多少種不同的方法爬到樓頂部？

【php算法學(xué)習(xí)之動(dòng)態(tài)規(guī)劃】相關(guān)文章：

php算法學(xué)習(xí)之寬度優(yōu)先搜索07-29

php學(xué)習(xí)之php配置07-15

PHP紅包算法11-04

php經(jīng)典算法介紹10-05

PHP經(jīng)典算法題09-05

PHP算法學(xué)習(xí)之分治法09-13

php學(xué)習(xí)之php預(yù)定義變量07-29

PHP幾個(gè)經(jīng)典算法題10-27

PHP的樹形結(jié)構(gòu)算法07-06