首页 ›存档› 技术 › 查看内容

php算法学习之动态规划

2018-3-30 13:00 |来自: 互联网 443 0

摘要: 动态规划程序设计是对解最优化问题的一种途径、一种方法，最终问题的最优解可以通过前面子问题的最优解推导出来。对于动态规划这个算法，自己学习的还不是很透彻，简单的总结自己学习的感受是：动态规划思想中融 ...

动态规划程序设计是对解最优化问题的一种途径、一种方法，最终问题的最优解可以通过前面子问题的最优解推导出来。

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

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

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

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

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

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

下面再来解一道比较有意思的问题，爬楼梯：
你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

--------------伟大的分割线----------------

PHP饭米粒(phpfamily) 由一群靠谱的人建立，愿为PHPer带来一些值得细细品味的精神食粮！

饭米粒只发原创或授权发表的文章，不转载网上的文章

所发的文章，均可找到原作者进行沟通。

也希望各位多多打赏（算作稿费给文章作者），更希望大家多多投搞。

投稿请联系：

本文由 ShutLove 向饭米粒投稿，转载请注明本来源信息和以下的二维码（长按可识别二维码关注）

本文转载于微信公众号: PHP饭米粒(phpfamily)，更多微信文章请扫描关注公众号:

声明：文章版权归原作者所有部分文章转自互联网如有侵权请联系 [邮箱地址] 删除

上一篇：昆明鞋包网科技有限公司下一篇：详解JavaScript跨域问题

相关分类