题目
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路
用Fib(n)表示青蛙跳上n阶台阶的跳法数,设定Fib(0) = 1;
当n = 1 时, 只有一种跳法,即1阶跳,即Fib(1) = 1;
当n = 2 时, 有两种跳的方式,一阶跳和二阶跳,即Fib(2) = Fib(1) + Fib(0) = 2;
当n = 3 时,有三种跳的方式,第一次跳出一阶台阶后,后面还有Fib(3-1)中跳法,第一次跳出二阶台阶后,后面还有Fib(3-2)中跳法,第一次跳出三阶台阶后,后面还有Fib(3-3)中跳法,即Fib(3) = Fib(2) + Fib(1)+Fib(0)=4;
当n = n 时,共有n种跳的方式,第一次跳出一阶台阶后,后面还有Fib(n-1)中跳法, 第一次跳出二阶台阶后,后面还有Fib(n-2)中跳法……………………..第一次跳出n阶台阶后,后面还有 Fib(n-n)中跳法,即Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+……….+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+…….+Fib(n-1)又因为Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+…….+Fib(n-2)故Fib(n) = 2*Fib(n-1) n >= 2
综上所述:
代码
#include <iostream>
using namespace std;
class Solution {
public:
int jumpFloorII(int number) {
if(number <= 0){
return 0;
}
else if(number == 1){
return 1;
}
return 2*jumpFloorII(number - 1);
}
};
int main(){
Solution s;
int number = 5;
cout<<s.jumpFloorII(number)<<endl;
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
变态跳台阶(python) 题目 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 思路 是斐波那契数列和跳台阶得升级版,详情在上篇和上上篇博客。 采用...
面试题 1:二维数组中的查找(考点: 数组) 1 面试题 2:替换空格(考点: 字符串) 2 面试题 3:从尾到头打印链表(考点: ...面试题 9:变态跳台阶(考点: 递归和循环) 8 面试题 10:矩形覆盖(考点: 递归和循环) 8
【Python学习-递归-斐波那契数列】【剑指offer】之跳台阶题目分析代码变态跳台阶分析代码矩形覆盖分析代码 题目 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序...
剑指offer 1.二位数组中的查找 2.替换空格 3.单链表:从尾到头打印链表 4.二叉树:重建二叉树 5.栈:用两个栈实现队列 6.旋转数组的最小数字 7.斐波那契数列 8.跳台阶 9.变态跳台阶 10.矩形覆盖 11.二进制中1的个数 12....
青蛙跳台阶和变态跳台阶(python、剑指Offer) 一、题目描述 青蛙跳台阶题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 变态跳...
剑指offer代码实现,通过。 # Title Solution Tag Note LeetCode 1 二维数组中的查找 数组 2 替换空格 字符串 3 从尾到头打印链表 链表 4 重建二叉树 树 5 用两个栈实现队列 栈和队列 LeetCode 232 6 旋转数组的最小...
Coding-InterviewsCoding-Interviews(剑指offer Java代码)二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的最小数字斐波那契数列跳台阶变态跳台阶矩形覆盖二进制中1的个数数值的...
每日刷题计划,记录做过的题目,内容包含剑指offer、程序员面试金典(CTCI)、数据结构 下面标题括号内的为对应包名 剑指offer(offer) java实现 03二维数组中的查找 04替换空格 05从尾到头打印链表 06重建二叉树 07用...
该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. Search a 2D Matrix II ...
《剑指Offer》 练习题 经典算法大全 leetcode 学习进度 ####递归 递归 cn.diyai.recursion.Recursion 斐波那契数列 跳台阶 cn.diyai.algorithmics.JumpTool 变态跳台阶 矩形覆盖 三角数字 阶乘 递归的二分查找 汉诺...
1、牛客网《剑指offer》二刷(二刷结束) 2、LeetCode (持续练习中,为了速度都是.java文件,不再写Markdown文件) 1、牛客网《剑指offer》二刷(二刷结束) 1、二维数组的查找 2、替换空格 3、从尾到头打印链表 4、...
剑指Offer 考点 题目 解法 难度 字符串 替换空格 易 字符串 字符串旋转 易 数组 二维数组中的查找 难 数组 旋转数组的最小数字 难 数组 打印1到最大的n位数 难 栈和队列 用两个栈实现队列 中 链表 从尾到头打印链表 ...
在指定空间中创建对象数组去重时间格式化获取字符串长度邮箱字符串判断颜色字符串转换字符串转为驼峰格式字符串字符统计剑指offer二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的...