内容简介:动态规划题第一天
2 0 1 9 -5 -15 星 期四 开 始 吧
动态规划题第一天
题 目 描 述
这是一个爬楼梯的问题,给定一个数字代表着楼梯的层数,每次你可以走一步或者两步,求最终你可以有几种方式到达顶峰。
看了一个专栏提到,关于解动态规划的题目可以从以下几点入手。
1.递归+记忆化 ->反向推出递推公式。
2.状态的定义 opt[n],dp[n].
3.状态转移的方程dp[n]=dp[n-1]+dp[n-2]
4.最优子结构
题 目 分 析
我们先用回溯法的思想来解,第n层台阶总的走法就等于它相邻台阶总走法+两阶台阶之外的走法,得出的递推公式.
f(n)=f(n-1)+f(n-2)
所以代码可以直接写出。
/** * @param Integer $n * @return Integer */ function climbStairs($n) { if($n<=1){ return 1; } return $this->climbStairs($n-1)+$this->climbStairs($n-2); }
但是这种递归的话进行了大量重复的运算,我们来看php的运行结果。你可以看到,当n等于44的时候运算超时了。
动态规划
动态规划最重要的两点就是状态的定义(有点飘)和递推的方程(递推公式很难推,学动态规划需要去大量的实战练习)。
f[n]=f[n-1]+f[n-2]
递推方程就是一个斐波那契数列
/** * @param Integer $n * @return Integer */ function climbStairs($n) { if($n<=1){ return 1; } $res[0]=1; $res[1]=1; for($i=2;$i<=$n;$i++){ $res[$i]=$res[$i-1]+$res[$i-2]; } return $res[$n]; }
Github整理地址: https://github.com/wuqinqiang/leetcode-php
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Leetcode动态规划之PHP解析(120. Triangle)
- 解析 :跻身数据科学领域的五条职业规划道路
- Leetcode动态规划之PHP解析(72. Edit Distance)
- Leetcode动态规划之PHP解析(152. Maximum Product Subarray)
- Leetcode动态规划之PHP解析(300. Longest Increasing Subsequence)
- Leetcode动态规划之PHP解析(123. Best Time to Buy and Sell Stock III)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Probability and Computing: Randomization and Probabilistic Techn
Michael Mitzenmacher、Eli Upfal / Cambridge University Press / 2017-7-3 / USD 62.23
Greatly expanded, this new edition requires only an elementary background in discrete mathematics and offers a comprehensive introduction to the role of randomization and probabilistic techniques in m......一起来看看 《Probability and Computing: Randomization and Probabilistic Techn》 这本书的介绍吧!