php算法学习之动态规划

动态规划程序设计是对解最优化问题的一种途径、一种方法，最终问题的最优解可以通过前面子问题的最优解推导出来。下面小编为大家整理了php算法学习之动态规划，希望能帮到大家！

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

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

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

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

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

应用分治法求解代码

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

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

我们定义了一个数组来记录斐波那契每个位置的值，这就相当于我们定义了一个状态；每个位置的值等于它前面两个的加和，这就相当于一个状态转移方程。

这里通过数组记录状态就是一种以空间换时间的.思想，其实和我们平时开发用到的缓存的设计很像。

总结动态规划求解可以分为4步：

1、确定要解决的子问题，即状态的定义。

2、列出状态转移方程。

3、根据给定条件，初始化已知状态值。

4、求解最终问题解。

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

你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？