列表

详情


DP3. 跳台阶扩展问题

描述

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

数据范围:
进阶:空间复杂度 , 时间复杂度

输入描述

本题输入仅一行,即一个整数 n 

输出描述

输出跳上 n 级台阶的跳法

示例1

输入:

3

输出:

4

示例2

输入:

1

输出:

1

原站题解

C 解法, 执行用时: 2ms, 内存消耗: 308KB, 提交时间: 2022-05-28

#include <stdio.h>
int f(int n) {
	int a[40] = { 0 }; 
	int i, j;
	a[0] = 1;
	for (i = 1; i < 40; i++) {
		a[i] = 2*a[i - 1];
	}
	return a[n - 1];
}
int main() {
	int n;
	scanf("%d", &n);
	printf("%d", f(n));
	return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2022-06-02

#include <stdio.h>
int main(){
    int n;
    while(scanf("%i",&n)!=EOF){
        //思路:dp[i]=dp[i-1]+dp[i-2]+...dp[1];dp[1]=1,dp[2]=2
        if(n<3){
            printf("%i",n);
        }else{
            int dp[n+1];
            dp[1]=1,dp[2]=2;
            for(int i=3;i<=n;++i){
                dp[i]=1;
                for(int j=i-1;j>0;--j){
                    dp[i] +=dp[j];
                }
            }
            printf("%i",dp[n]);
        }
    }
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2022-05-16

#include<stdio.h>
int main() {
	int n, i = 1;
	scanf("%d", &n);
	n--;
	while (n--)
	{
		i *= 2;
	}
	printf("%d", i);
	return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2022-03-29

#include <stdio.h>
int fun(int data)
{
    int sum = 0;
    if(data == 1 ||data == 0)
        return data;
        sum = fun(data-1)*2;
    
    return sum;
}
int main()
{
    int n = 0;
    scanf("%d",&n);
    printf("%d",fun(n));
}

C 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2022-03-28

#include <stdio.h>
#include <assert.h>
int main(void)
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        assert(n>0 && n<=20);
        printf("%d\n", 1 << n-1);
    }
    return 0;
}

上一题