首页 > 试题广场 >

跳台阶扩展问题

[编程题]跳台阶扩展问题

热度指数：694014 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

数据范围： $1 \le n \le 20$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(1)$

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

推荐

dangle

关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:

f(1) = 1

f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。

f(3) = f(3-1) + f(3-2) + f(3-3)

...

f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)

说明：

1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的跳法数。

2）n = 1时，只有1种跳法，f(1) = 1

3) n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1），f(2) = f(2-1) + f(2-2)

4) n = 3时，会有三种跳得方式，1阶、2阶、3阶，

那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)

因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)

5) n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：

f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)

6) 由以上已经是一种结论，但是为了简单，我们可以继续简化：

f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)

可以得出：

f(n) = 2*f(n-1)

7) 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：

| 1 ,(n=0 )

f(n) = | 1 ,(n=1 )

| 2*f(n-1),(n>=2)

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);
        }
    }
}

编辑于 2015-06-17 21:30:40 回复(217)

Java

YuyangXin

最后会发现方法的种数 = 2的n-1次方，所以：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    public int jumpFloorII (int number) {
        // write code here
        return (int)Math.pow(2,number-1);
    }
}

发表于 2024-08-17 14:11:10 回复(0)

Java

୧⍢⃝୨

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    public int jumpFloorII (int number) {
        int[] dp = new int[number+1];
        dp[0] = 1;
        for(int i=1;i<=number;i++){
            for(int j=i-1;j>=0;j--){
                dp[i] += dp[j];
            }
        }
        return dp[number];
    }
}

发表于 2024-08-04 14:33:30 回复(0)

Java

有力量的王老五年薪百万

public int jumpFloorII (int number) {

// write code here

int pre = 1;

int sum = 1;

for (int i = 2; i <= number; i ++) {

sum = 2 * pre;

pre = sum;

}

return sum;

}

编辑于 2024-03-16 17:25:49 回复(0)

Java

叁秋本

return (int)Math.pow(2,number-1)

发表于 2023-08-14 14:24:24 回复(0)

Java

顾悦希

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param number int整型

* @return int整型

public int jumpFloorII (int number) {

// 位操作

return 1<<(number-1);

}

发表于 2023-08-05 21:48:18 回复(0)

Java

dalerambo

根据递推公式可以得到数列的通项是f(n) = 2^n-1，直接用位移运算即可

public class Solution {
    public int jumpFloorII(int target) {
        if(target <= 0) {
            return 0;
        }

        return 1<<(target-1);
    }

}

时间复杂度O(1)，空间复杂度O(1)

发表于 2023-06-02 11:26:30 回复(0)

Java

牛客200024454号

int jumpFloorII(int number) {

// write code here

if (number <= 2) return number;

return jumpFloorII(number - 1) << 1;

}

f(n) = f(1) + f(2) + ... + f(n - 2) + f(n - 1)

f(n - 1) = f(1) + f(2) + ... + f(n - 2) 相减得

f(n) = 2f(n - 1)

发表于 2022-12-08 15:38:27 回复(0)

Java

牛客用户007

import java.util.*;
public class Solution {
    public int jumpFloorII(int target) {
        if(target == 1) return 1;
        if(target == 2) return 2;
        int[] dp = new int[target + 1];
        Arrays.fill(dp,1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < target + 1; i ++) {
            for (int j = 1; j < i; j ++) {
                dp[i] = dp[i] +  dp[j];
            }
        }
        return dp[target];
    }
}

发表于 2022-09-13 14:04:46 回复(0)

Java

小泽玛丽恩

public class Solution {
public int jumpFloorII(int target) {
return 1 << (target - 1);
}
}

发表于 2022-05-21 11:43:39 回复(0)

Java

来学习的小张

public class Solution {
    public int jumpFloorII(int target) {
        return (int)Math.pow(2,target - 1);
    }
}

发表于 2022-05-04 19:59:14 回复(0)

Java

镜花水月_

//每集台阶都有踩与不踩两种情况，n级台阶就是2的n次方，但是最后一个台阶是必须踩的，所以n-1个台阶需要踩，即2的n-1次方，即1<<(n-1)

public class Solution {
    public int jumpFloorII(int target) {
        if(target == 1)
            return 1;
        int[] arr = new int[target]; //状态：跳上n节台阶的方法个数为arr[n-1]
        arr[0] = 1;  //初始化
        for(int i = 1;i<target;i++){
            arr[i] = 2*arr[i-1];//状态转移方程
        }
        return arr[target-1]; //返回值
    }
}

发表于 2022-04-20 12:13:46 回复(0)

Java

hhhhh.

public class Solution {
    public int jumpFloorII(int target) {
        if(target == 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;
        int[] dp = new int[target];
        dp[0] = 1;
        dp[1] = 2;
        int j = 1;
        for(int i = 2;i < target;i++){
            dp[i] = 1; //跳n级的时候
            while(j < target && i - j >= 0){
                dp[i] += dp[i - j];
                j++;
            }
            j = 1;
        }
        return dp[target - 1];
    }
}

发表于 2022-04-17 13:03:31 回复(0)

Java

世界杯2009

import java.util.*;
public class Solution {
    public int jumpFloorII(int target) {
        if (target <= 2) {
            return target;
        }
        // dp[i]代表到i+1台阶有多少种跳法
        int[] dp = new int[target];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < target; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[i - j];
            }
            // 必须要加1，代表一下跳到i层
            dp[i] += 1;
        }
        //System.out.println(Arrays.toString(dp));
        return dp[dp.length - 1];
    }

}

发表于 2022-04-10 15:06:13 回复(0)

Java

牛客839070574号

return (1 << target) >> 1;

发表于 2022-03-30 10:03:07 回复(0)

Java

勇敢的心。

public class Solution {
    int n,cot=0;
    public int jumpFloorII(int target) {
        n=target;    //传给全局变量，方便dfs中比对
        dfs(0);
        return cot;
    }

    private void dfs(int sum) {
        if(sum>n) return;    // 跳多了，碰壁返回
        if(sum==n){         // 刚好跳中，新的情况所以要记录，然后也返回
            cot++;
            return;
        }
        for(int i=1;i<=n;i++){  //1~n每种跳法都尝试一遍
            dfs(sum+i);
        }
    }
}

发表于 2022-01-21 12:01:33 回复(0)

Java

是小王吖🐅

public class Solution {
    private int rst=0;
    public int jumpFloorII(int target) {
        for(int s=1;s<=target;s++)
            dfs(target,s);
        return rst;
    }
    public void dfs(int target,int diff){
     int tmp=target-diff;
        if(tmp==0)
            rst++;
        else if(tmp<0)
            return;
        else{
            for(int i=1;i<=tmp;i++)
                dfs(tmp,i);
        }
    }
}

发表于 2022-01-15 20:15:16 回复(0)

Java

王小汪

可以看做是跳台阶问题的变种。

跳台阶，每次只能跳一个或两个台阶：

dp[i] = dp[i - 1] + dp[i - 2];

每次可以跳任意个：

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4] + ... + dp[1] + 1;

最后+1 表示一步跳到顶。

可以发现规律：

target res

1 1

2 2

3 2 + 1 + 1 = 4

4 4 + 2 + 1 + 1 = 8

5 8 + 4 + 2 + 1 + 1 = 16

所以直接返回2的(n - 1)次方就可以了。

public int jumpFloorII(int target) {
    return 1 << (target - 1);
}

发表于 2022-01-05 00:10:34 回复(0)

Java

浮鸟(BAT实习ing，目标外企~)

public class Solution {
    public int jumpFloorII(int target) {
        // 分析得到（1）式：f(n) = f(n-1) + f(n-2) +....+f(0)
        // 统一减个1，得到（2）式：f(n-1) = f(n-2) + f(n-3) +......+f(0)
        // （1）-（2）得到：f(n) = 2 f(n-1)，以此为基础，构建代码：
        if(target==0){
            return 0;
        }
        // 根据表达式，只需要一个指针就可以了
        int sum = 1;
        for(int i=1;i<target;i++){
            sum = 2 * sum;
        }
        return sum;
    }
}

发表于 2022-01-02 18:30:20 回复(0)