php演算法學習之動態規劃

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

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

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

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

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

先來一個最常見的題體驗一下，求斐波那契數列（不知道的同學請自行百度一下）某個位置的值？
應用分治法求解程式碼

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

ok，下面我們來看看動態規劃如何進行最佳化。

 我們定義了一個陣列來記錄斐波那契每個位置的值，這就相當於我們定義了一個狀態；每個位置的值等於它前面兩個的加和，這就相當於一個狀態轉移方程式。
這裡透過陣列記錄狀態就是一種以空間換時間的思想，其實和我們平常開發用到的快取的設計很像。

總結動態規劃求解可以分為4步驟：
1、確定要解決的子問題，即狀態的定義。
2、列出狀態轉移方程式。
3、根據給定條件，初始化已知狀態值。
4、求解最終問題解。

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

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