这篇文章主要介绍“C++怎么解决爬楼梯问题”,在日常操作中,相信很多人在C++怎么解决爬楼梯问题问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C++怎么解决爬楼梯问题”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!Example 1:Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 stepsExample 2:Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step这篇博客最开始名字叫做爬梯子问题,总是有童鞋向博主反映移动端打不开这 香港云主机篇博客,博主觉得非常奇怪,自己也试了一下,果然打不开。心想着是不是这个博客本身有问题,于是想再开一个相同的帖子,结果还是打不开,真是见了鬼了。于是博主换了个名字,结果居然打开了?!进经过排查后发现,原来是“爬梯子”这三个字是敏感词,放到标题里面,博客就被屏蔽了,我也真是醉了,完全是躺枪好么,无奈之下,只好改名为爬楼梯问题了 -。-|||。这个爬梯子问题最开始看的时候没搞懂是让干啥的,后来看了别人的分析后,才知道实际上跟斐波那契数列非常相似,假设梯子有n层,那么如何爬到第n层呢,因为每次只能爬1或2步,那么爬到第n层的方法要么是从第 n-1 层一步上来的,要不就是从 n-2 层2步上来的,所以递推公式非常容易的就得出了:dp[n] = dp[n-1] + dp[n-2]。 由于斐波那契额数列的求解可以用递归,所以博主最先尝试了递归,拿到 OJ 上运行,显示 Time Limit Exceeded,就是说运行时间超了,因为递归计算了很多分支,效率很低,这里需要用动态规划 (Dynamic Programming) 来提高效率,代码如下:C++ 解法一:Java 解法一:我们可以对空间进行进一步优化,只用两个整型变量a和b来存储过程值,首先将 a+b 的值赋给b,然后a赋值为原来的b,所以应该赋值为 b-a 即可。这样就模拟了上面累加的过程,而不用存储所有的值,参见代码如下:C++ 解法二:Java 解法二:虽然前面说过递归的写法会超时,但是只要加上记忆数组,那就不一样了,因为记忆数组可以保存计算过的结果,这样就不会存在重复计算了,大大的提高了运行效率,其实递归加记忆数组跟迭代的 DP 形式基本是大同小异的,参见代码如下:C++ 解法三:Java解法三:论坛上还有一种分治法 Divide and Conquer 的解法,用的是递归形式,可以通过,但是博主没有十分理解,希望各位看官大神可以跟博主讲一讲~C++ 解法四:Java 解法四:其实斐波那契数列是可以求出通项公式的,推理的过程请参见 知乎上的这个贴子,那么有了通项公式后,直接在常数级的时间复杂度范围内就可以求出结果了,参见代码如下:C++ 解法五:Java 解法五:到此,关于“C++怎么解决爬楼梯问题”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注开发云网站,小编会继续努力为大家带来更多实用的文章!
相关推荐: win10的Windows Defender怎么使用
本文小编为大家详细介绍“win10的Windows Defender怎么使用”,内容详细,步骤清晰,细节处理妥当,希望这篇“win10的Windows Defender怎么使用”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。具体操作:…
免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。