[已解决]求解递归问题

白痴爱面包

组长很喜欢爬楼梯，但是由于其腿不够长，每次最多只能一步跨越两个阶梯。比如他初始在楼底，跨越一个阶梯到达 1 号阶
梯，或者跨越两个阶梯到达 2号阶梯。由于他非常无聊，想把所有不同的到达楼顶的方式都尝试一遍。
但是他又很懒，不想自己计算，因此请你帮他算一算，对于一共有 n 个阶梯的楼梯，一共有多少总方法从楼底到达楼顶。
由于最后答案可能很大，输出最后的答案对 100007 取模的结果。

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-15 19:53:28

isdkz 发表于 2023-4-15 19:51
这个问题可以用递归或者动态规划来求解。由于递归可能会产生很多重复计算，我们选择使用动态规划方法。这里 ...

这是C语言版本：

#include <stdio.h>

// 计算有多少种方法到达楼顶的函数
int climb_stairs(int n) {
    if (n <= 2) {
        return n;
    }

    int dp[n + 1]; // 定义动态规划数组
    dp[1] = 1;
    dp[2] = 2;

    // 从第3阶开始，计算到达每个阶梯的方法数
    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 100007; // 更新动态规划数组，取模100007防止整数溢出
    }

    return dp[n];
}

int main() {
    int n;
    printf("请输入楼梯的阶梯数: ");
    scanf("%d", &n);

    int result = climb_stairs(n);
    printf("一共有 %d 种方法到达楼顶。\n", result);

    return 0;
}

跳转到最佳答案楼层

sfqxx

可以使用动态规划来解决这个问题。对于第 i 个楼梯（从第 0 个开始计数），设 s[i] 表示从楼底到达该楼梯的所有方法的数量。则有 s[0]=1，s[1]=1，s[2]=2，对于 i>2，有以下转移方程：

s[i] = (s[i-1] + s[i-2]) % 100007

最终答案为 s[n]，其中 n 为楼梯总数。下面是具体的 Python 代码实现：

MOD = 100007

def climb_stairs(n):
    if n == 0 or n == 1:
        return 1
    if n == 2:
        return 2

    s = [0] * (n+1)
    s[0] = 1
    s[1] = 1
    s[2] = 2

    for i in range(3, n+1):
        s[i] = (s[i-1] + s[i-2]) % MOD

    return s[n]

# 测试样例
print(climb_stairs(3)) # 输出为 3

在上面的代码中，MOD 是取模的数。当 n=0 或 n=1 时，只有一种到达楼顶的方法，因此直接返回 1；当 n=2 时，有两种到达楼顶的方法，直接返回 2。对于 i>2，使用循环计算 s 数组并利用取模运算避免答案过大的问题。最后返回 s[n] 即可。
有用请设置最佳答案

isdkz

这个问题可以用递归或者动态规划来求解。由于递归可能会产生很多重复计算，我们选择使用动态规划方法。这里是一个Python程序，可以求解这个问题：

def climb_stairs(n):
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 100007

    return dp[n]

n = int(input("请输入楼梯的阶梯数: "))
result = climb_stairs(n)
print("一共有 %d 种方法到达楼顶。" % result)

使用这个程序，你可以计算出对于给定楼梯数 n 的情况下，有多少种不同的方式到达楼顶。最后的答案会对 100007 取模。

isdkz

isdkz 发表于 2023-4-15 19:51
这个问题可以用递归或者动态规划来求解。由于递归可能会产生很多重复计算，我们选择使用动态规划方法。这里 ...

这是C语言版本：

#include <stdio.h>

// 计算有多少种方法到达楼顶的函数
int climb_stairs(int n) {
    if (n <= 2) {
        return n;
    }

    int dp[n + 1]; // 定义动态规划数组
    dp[1] = 1;
    dp[2] = 2;

    // 从第3阶开始，计算到达每个阶梯的方法数
    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 100007; // 更新动态规划数组，取模100007防止整数溢出
    }

    return dp[n];
}

int main() {
    int n;
    printf("请输入楼梯的阶梯数: ");
    scanf("%d", &n);

    int result = climb_stairs(n);
    printf("一共有 %d 种方法到达楼顶。\n", result);

    return 0;
}

isdkz

isdkz 发表于 2023-4-15 19:53
这是C语言版本：

这是递归版本：

#include <stdio.h>

// 计算递归方法的函数
int climb_stairs_recursive(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }

    // 递归调用
    return (climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)) % 100007;
}

int main() {
    int n;
    printf("请输入楼梯的阶梯数: ");
    scanf("%d", &n);

    int result = climb_stairs_recursive(n);
    printf("一共有 %d 种方法到达楼顶。\n", result);

    return 0;
}

白痴爱面包

isdkz 发表于 2023-4-15 19:51
这个问题可以用递归或者动态规划来求解。由于递归可能会产生很多重复计算，我们选择使用动态规划方法。这里 ...

我希望得到用c或c++写的代码,动态管理不懂，递归最好

isdkz

白痴爱面包 发表于 2023-4-15 20:03
我希望得到用c或c++写的代码,动态管理不懂，递归最好

我在最后面发了一个递归版本

柿子饼同学

#include <bits/stdc++.h>
using namespace std;

const int mod = 100007;

int climb(int stair){
    if(stair <= 1) return 1;
    // 递归边界, 小于 1 就只有一种方法了
    return (climb(stair - 1) + climb(stair - 2)) % mod;
    // 走到这个台阶的方法数是 stair-1 阶方法数 + stair-2 阶方法数
}
int n;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    cout << climb(n);
    
    return 0;
}