一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
数据范围：
要求：时间复杂度：)
，空间复杂度： )
[编程题]跳台阶
青蛙跳台阶
划分子问题:
一层：1
二层：11 2
三层：111 12
四层：1111 112 22
五层：11111 1112 122
......
仔细想一想：
从三层楼开始：
不管是有几层楼梯，都是要选择先跳一层还是先跳两层
假如我先跳一层，子问题就变成了f(n-1)个跳法的问题，
假如我先
展开全文
这题和前面 DP1 斐波那契数列基本上是一样的，不同的是，这里斐波那契数列的起始项是1,2,3,5,8，我们把它改一下即可
解法一
题中要求的是 空间复杂度 O(1) ，很明显使用递归是行不通的，我们先改成非递归的看一下（这种复杂度也是不行的，我们先看一下代码）
import java.util.S
展开全文
因为是 dp ，所以先来划分子问题：
假设跳 nnn 个台阶的跳法总数为 fnf_nfn ，
那么 f1=1f_1=1f1=1 （跳 111 阶只有一种方法），f2=2f_2=2f2=2（跳 222 阶有两种方法：1 1 和 2 ）。
尝试列出几个 nnn ：
f1=1f_1=1f1=1 ；
展开全文
本题与斐波那契数列相似，不同的是是以1,2,3,5开始。
那么首先回忆一下斐波那契数列，作为dp的入门题，斐波那契作为数学和许多书中的动归入门题
相信递归的方程式对于大家而言并不难
就是dp[i]=dp[i-1]+dp[i-2];
#include<iostream>
展开全文
public class Main {
public static void main(String[] args) {
展开全文
#include<stdio.h>
int fun(int n)
{
if(n==1)
return 1;
else if(n==2)
return 2;
else
return fun(n-2)+fun(n-1);
}
int main()
{
int n;
scanf("%d",&a
展开全文
#include<bits/stdc++.h>
using namespace std;
long long a[55]={0,1,2},n;
int main()
{
for(int i=3;i<=50;i++)
a[i]=a[i-1]+a[i-2];
while(cin
展开全文
a_list = [1, 1]
n = int(input())
if n < 2:
print(n)
else:
for i in range(2, n+1):
a_list.append(a_list[i-1] + a_list[i-2])
prin
展开全文
问题信息
难度：
40条回答
66收藏
5575浏览
通过挑战的用户
查看代码-
2022-10-23 17:38:24
-
2022-09-22 10:46:55
-
2022-09-16 14:18:32 -
2022-09-15 23:37:18
-
2022-09-15 22:37:57
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
