一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
用f(n)表示n级台阶的总共跳法。
第一次：
跳1级，剩下n-1级未跳，剩下的跳法是f(n-1)
跳2级，剩下n-2级未跳，剩下的跳法是f(n-2)
跳n-1级, 剩下1级未跳，剩下的跳法是f(1)
由此可以推出f(n) = f(n-1) + f(n-2) + ...... + f(1)
也可以推出f(n-1) = f(n-2) + f(n-3) + ...... + f(1)
f(n) = 2 * f(n-1)
因此我们也可以推出
f(n-1) = 2 * f(n-2)
f(n-2) = 2 * f(n-3)
......
f(2) = 2 * f(1)
因此最后结果是
f(n) = 2n-1
class Solution {
public:
int jumpFloorII(int n) {
return 1<<(n-1);
}
};
本文首发于我的个人博客：尾尾部落 题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该...
题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳...
题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种...
本文首发于我的个人博客Suixin’s Blog原文: https://suixinblog.cn/2019/03...
剑指offer 动态规划 Python and C++ 1、斐波拉契数列2、跳台阶3、变态跳台阶4、矩阵覆盖 斐波...
写在前面： 为了增长一下自己的数据结构能力，也为了面试准备，准备将剑指Offer做一下，并与各位分享，希望各位可以...
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法...
题目 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法...
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 经...
9. 变态跳台阶 题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级...
本文标题：剑指offer 变态跳台阶
本文链接：https://www.haomeiwen.com/subject/tuphbxtx.html
网友评论