php算法学习之动态规划
动态规划程序设计是对解最优化问题的一种途径、一种方法,最终问题的最优解可以通过前面子问题的最优解推导出来。下面小编为大家整理了php算法学习之动态规划,希望能帮到大家!
对于动态规划这个算法,自己学习的还不是很透彻,简单的总结自己学习的感受是:
动态规划思想中融合了递归和分治的思想,但不同于分治的是,动态规划求解中会通过状态记录求解过程中每一个分支的最优解法,以此节省了许多分支的重复计算。
动态规划最重要同样也是最难的两步是找到描述子问题的状态以及状态间的推导关系。
比较可能使用动态规划的问题:求最大最小值、是否有可行方案以及可行方案个数。
先来一个最常见的题体验一下,求斐波那契数列(不知道的同学请自行百度一下)某个位置的值?
应用分治法求解代码
分治求解过程中,会有许多重复的运算,如下图3和2都被重复运算了两次,index值越大重复计算的次数就越多。
ok,下面我们看一下动态规划如何进行优化。
我们定义了一个数组来记录斐波那契每个位置的值,这就相当于我们定义了一个状态;每个位置的值等于它前面两个的加和,这就相当于一个状态转移方程。
这里通过数组记录状态就是一种以空间换时间的.思想,其实和我们平时开发用到的缓存的设计很像。
总结动态规划求解可以分为4步:
1、确定要解决的子问题,即状态的定义。
2、列出状态转移方程。
3、根据给定条件,初始化已知状态值。
4、求解最终问题解。
下面再来解一道比较有意思的问题,爬楼梯:
你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?
-
PHP中超全局变量$GLOBALS和global的区别
人之所以能,是相信能。努力总是会有收获的。下面是小编整理的PHP中超全局变量$GLOBALS和global的区别,希望对大家有用,更多消息请关注应届毕业生网。一、超全局变量$GLOBALSPHP超全局变量有很多,如下的都属于超全局变量(Superglobal):$GLOBALS,$_SERVER,$_GET,$_POST,$_...
-
php如何基于dom实现图书xml格式数据
导语:php如何基于dom实现图书xml格式数据呢?下面是小编给大家提供的代码实现方法,大家可以参考阅读,更多详情请关注应届毕业生考试网。<?php$doc=newDOMDocument();$doc->load('');$books=$doc->getElementsByTagName("book");foreach($booksas$book){$aut...
-
PHP代码如何规范
对于PHP入门学习的童鞋来说,基础是很重的,一定要打好基础。那么大家知道PHP代码如何规范呢?下面一起来看看!了解PHP开发规范可以少走很多弯路,网上各种PHP开发规范也很多,我结合自身使用PHP的情况,来说说我所理解的PHP开发规范,涉及多个方面,比如PHP代码规范、PHP文件...
-
ThinkPHP中自动验证
学无止境,刚开始学习PHP会觉得简单,但是越学会越难。下面是小编整理的关于ThinkPHP中自动验证的知识,希望对大家有用,更多消息请关注应届毕业生网。ThinkPHP中自动验证:array(‘字段’,‘验证规则’,‘错误提示’[,‘验证条件&rsqu...