php算法学习之动态规划

对于动态规划这个算法，自己学习的还不是很透彻，简单的总结自己学习的感受是：

动态规划思想中融合了递归和分治的思想，但不同于分治的是，动态规划求解中会通过状态记录求解过程中每一个分支的最优解法，以此节省了许多分支的重复计算。

动态规划最重要同样也是最难的两步是找到描述子问题的状态以及状态间的推导关系。

比较可能使用动态规划的问题：求最大最小值、是否有可行方案以及可行方案个数。

先来一个最常见的题体验一下，求斐波那契数列（不知道的同学请自行百度一下）某个位置的值？
应用分治法求解代码

分治求解过程中，会有许多重复的运算，如下图3和2都被重复运算了两次，index值越大重复计算的次数就越多。

ok，下面我们看一下动态规划如何进行优化。

我们定义了一个数组来记录斐波那契每个位置的值，这就相当于我们定义了一个状态；每个位置的值等于它前面两个的加和，这就相当于一个状态转移方程。
这里通过数组记录状态就是一种以空间换时间的思想，其实和我们平时开发用到的缓存的设计很像。

总结动态规划求解可以分为4步：
1、确定要解决的子问题，即状态的定义。
2、列出状态转移方程。
3、根据给定条件，初始化已知状态值。
4、求解最终问题解。

下面再来解一道比较有意思的问题，爬楼梯：

以上就是php算法学习之动态规划的内容，更多相关内容请关注PHP中文网（www.gxlcms.com）！