动态规划程序设计是对解最优化问题的一种途径、一种方法，最终问题的最优解可以通过前面子问题的最优解推导出来。
对于动态规划这个算法，自己学习的还不是很透彻，简单的总结自己学习的感受是：
动态规划思想中融合了递归和分治的思想，但不同于分治的是，动态规划求解中会通过状态记录求解过程中每一个分支的最优解法，以此节省了许多分支的重复计算。
动态规划最重要同样也是最难的两步是找到描述子问题的状态以及状态间的推导关系。
比较可能使用动态规划的问题：求最大最小值、是否有可行方案以及可行方案个数。
立即学习“PHP免费学习笔记（深入）”；
先来一个最常见的题体验一下，求斐波那契数列（不知道的同学请自行百度一下）某个位置的值？
应用分治法求解代码
分治求解过程中，会有许多重复的运算，如下图3和2都被重复运算了两次，index值越大重复计算的次数就越多。
ok，下面我们看一下动态规划如何进行优化。
我们定义了一个数组来记录斐波那契每个位置的值，这就相当于我们定义了一个状态；每个位置的值等于它前面两个的加和，这就相当于一个状态转移方程。
这里通过数组记录状态就是一种以空间换时间的思想，其实和我们平时开发用到的缓存的设计很像。
总结动态规划求解可以分为4步：
1、确定要解决的子问题，即状态的定义。
2、列出状态转移方程。
3、根据给定条件，初始化已知状态值。
4、求解最终问题解。
下面再来解一道比较有意思的问题，爬楼梯：
以上就是php算法学习之动态规划的内容，更多相关内容请关注PHP中文网（www.php.cn）！
PHP怎么学习？PHP怎么入门？PHP在哪学？PHP怎么学才快？不用担心，这里为大家提供了PHP速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
885
收藏
