博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
剑指offer :跳台阶
阅读量:5807 次
发布时间:2019-06-18

本文共 640 字,大约阅读时间需要 2 分钟。

这题之前刷leetcode也遇到过,感觉是跟斐波拉契差不多的题。

题目描述:

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

 

解题思路:

这类题一般就是用递归思想,先考虑跳一级台阶情况,再是两级。发现由于跳台阶的选择只有1级和2级,所以其实跳n级台阶就是跳n-1级和n-2级的和。

本科做斐波拉契用递归时已经知道会超时,由于分别计算f(n-1)和f(n-2)实际是重复计算了,所以用数组去存每次的计算结果,直接调用就可以。

 

代码:

class Solution {public:    int jumpFloor(int number) {        vector
sum_jump; sum_jump.push_back(0); sum_jump.push_back(1); sum_jump.push_back(2); for(int i=3; i<=number; i++) { sum_jump.push_back(sum_jump[i-1]+sum_jump[i-2]); } return sum_jump[number]; }};

 

转载于:https://www.cnblogs.com/LJ-LJ/p/10585462.html

你可能感兴趣的文章
livemesh在远程桌面中的运用
查看>>
蜜罐技术的配置模式和信息收集
查看>>
查看Oracle的实例名
查看>>
Zend Studio去除编辑器的语法警告
查看>>
linux驱动current关键词
查看>>
让SQL再快一点儿
查看>>
而尔维尔
查看>>
ios获取手机状态 idfa idfv 网络类型 分辨率 获取运营商 ip
查看>>
微信小程序下nginx代理wss,实现兼容原本服务协议ws,Java版本
查看>>
Linux RPS RFS
查看>>
通过Secure CRT导出设备配置
查看>>
我的友情链接
查看>>
jmeter从上一个请求使用正则表达式抓取Set-Cookie值,在下一个请求中运用
查看>>
【Mybatis框架】输入映射-pojo包装类型
查看>>
js 动态添加input代码
查看>>
oldboy 27期学习计划
查看>>
我的友情链接
查看>>
Caused by: javax.el.ELException:
查看>>
我的友情链接
查看>>
【Nocti推荐】Sublime text!超赞代码编辑器
查看>>