一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
数据范围：
进阶：空间复杂度%20)
， 时间复杂度 )
进阶：空间复杂度
[编程题]跳台阶扩展问题
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)
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)
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)
//每集台阶都有踩与不踩两种情况，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)
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)
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)
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)
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)
可以看做是跳台阶问题的变种。
跳台阶，每次只能跳一个或两个台阶：
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)
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)
问题信息
通过挑战的用户
查看代码-
2023-03-12 21:49:38 -
2023-03-12 20:54:12
-
2023-03-11 09:50:24
-
2023-03-09 14:31:24
-
2023-03-09 10:13:01
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
关于本题，前提是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 )
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); } } }