变态跳台阶题目描述解题思路

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路

思路一：规模从小到大列举，记台阶数为n，记跳法共有f(n)种:
f(0) = 1
n = 1时，总共有f(1) = 1种跳法
n = 2时，总共有f(2) = f(1) + f(0)
n = 3时，总共有f(3) = f(2) + f(1) + f(0)
…
这里解释一下为什么要有f(0)以及为什么有这样的规律的原因：根据题目可知青蛙可以任意跳台阶，那么每增加一级台阶青蛙就可以从之前所有的级跳法中跳到这一级（例：n=4时，青蛙就可以f(3)的任意一种跳法上跳过来，可以从f(2)的任意一种跳法上跳过来，也可以从f(1)的任意一种跳法上跳过来，f(0)代表从起始位置跳过来。那么f(4)就等于f(3)+f(2)+f(1)+f(0)）。
思路理清楚后就有了以下的式子：
f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(0)
f(n-1) = f(n-2) + f(n-3) + f(n-4) + … + f(0)
将下面一行带入到上面一行得到以下迭代式：
f(n) = 2f(n-1)，n>=2
f(1) = 1
f(0) = 0
代码如下：

public class Solution {
    public int JumpFloorII(int target) {
        if (target <= 0) {
            return -1;
        }else if(target == 1) {
            return 1;
        }else {
            return 2 * JumpFloorII(target - 1);
        }
    }
}

思路二：对于第n级台阶来说，可以确定这一级青蛙一定要跳上来，前n-1级台阶每级都可以有存在和不存在两种形态，n-1级台阶就有2^(n-1)种情况。其实我们所要求的序列为：0,1,2,4,8,16,……，这样规律就和思路一一样了。

最后

以上就是粗犷水壶为你收集整理的变态跳台阶题目描述解题思路的全部内容，希望文章能够帮你解决变态跳台阶题目描述解题思路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。