php算法學習之動態規劃

php算法學習之動態規劃

　　動態規劃程序設計是對解最優化問題的一種途徑、一種方法，最終問題的最優解可以通過前面子問題的最優解推導出來。下面小編為大家整理了php算法學習之動態規劃，希望能幫到大家！

php算法學習之動態規劃

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

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

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

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

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

　　應用分治法求解代碼

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

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

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

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

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

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

　　2、列出狀態轉移方程。

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

　　4、求解最終問題解。

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

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

【php算法學習之動態規劃】相關文章：