欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer 变态跳台阶 (经典跳台阶问题)Java

程序员文章站 2022-07-10 14:34:45
...

题目描述

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


题解

设f[i] 表示 当前跳道第 i 个台阶的方法数。那么f[n]就是所求答案。
假设现在已经跳到了第 n 个台阶,那么前一步可以从哪些台阶到达呢?

如果上一步跳 1 步到达第 n 个台阶,说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为f[n-1]
如果上一步跳 2 步到达第 n 个台阶,说明上一步在第 n-2 个台阶。已知跳到第n-2个台阶的方法数为f[n-2]
……
如果上一步跳 n 步到达第 n 个台阶,说明上一步在第 0 个台阶。已知跳到 第0个台阶的方法数为f[0]

那么总的方法数就是所有可能的和。也就是f[n] = f[n-1] + f[n-2] + … + f[1]

在得出公式之后我们可以进行化简:
f[n] = f[n-1] + f[n-2] + … + f[1]
f[n-1] = f[n-2] + f[n-2] + … + f[1]
我们使用第一个式子减去第二个式子得出: f[n] = 2 * f[n-1];
进行整理之后得出最后的解为:f[n] = 2(n-1)


代码

public class Solution {
    public int JumpFloorII(int target) {
        double num = Math.pow(2.0,(double)(target-1));
        return (int)num;
    }
}