動態規劃程序設計是對解最優化問題的一種途徑、一種方法，最終問題的最優解可以通過前面子問題的最優解推導出來。

對于動態規劃這個算法，自己學習的還不是很透徹，簡單的總結自己學習的感受是：

動態規劃思想中融合了遞歸和分治的思想，但不同于分治的是，動態規劃求解中會通過狀態記錄求解過程中每一個分支的最優解法，以此節省了許多分支的重復計算。

動態規劃最重要同樣也是最難的兩步是找到描述子問題的狀態以及狀態間的推導關系。

比較可能使用動態規劃的問題：求最大最小值、是否有可行方案以及可行方案個數。

先來一個最常見的題體驗一下，求斐波那契數列(不知道的同學請自行百度一下)某個位置的值？

應用分治法求解代碼

分治求解過程中，會有許多重復的運算，如下圖3和2都被重復運算了兩次，index值越大重復計算的次數就越多。

ok，下面我們看一下動態規劃如何進行優化。

我們定義了一個數組來記錄斐波那契每個位置的值，這就相當于我們定義了一個狀態；每個位置的值等于它前面兩個的加和，這就相當于一個狀態轉移方程。

這里通過數組記錄狀態就是一種以空間換時間的思想，其實和我們平時開發用到的緩存的設計很像。

總結動態規劃求解可以分為4步：

1、確定要解決的子問題，即狀態的定義。

2、列出狀態轉移方程。

3、根據給定條件，初始化已知狀態值。

4、求解最終問題解。

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

以上就是php算法學習之動態規劃的內容，更多相關內容請關注PHP中文網(www.php.cn)！

本文原創發布php中文網，轉載請注明出處，感謝您的尊重！

總結

以上是生活随笔為你收集整理的php算法学习,php算法学习之动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。