[已解决]求解递归问题

白痴爱面包

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

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-15 19:53:28

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

这是C语言版本：

1. #include <stdio.h>
   
2. 
   
3. // 计算有多少种方法到达楼顶的函数
   
4. int climb_stairs(int n) {
   
5.     if (n <= 2) {
   
6.         return n;
   
7.     }
   
8. 
   
9.     int dp[n + 1]; // 定义动态规划数组
   
10.     dp[1] = 1;
    
11.     dp[2] = 2;
    
12. 
    
13.     // 从第3阶开始，计算到达每个阶梯的方法数
    
14.     for (int i = 3; i <= n; i++) {
    
15.         dp[i] = (dp[i - 1] + dp[i - 2]) % 100007; // 更新动态规划数组，取模100007防止整数溢出
    
16.     }
    
17. 
    
18.     return dp[n];
    
19. }
    
20. 
    
21. int main() {
    
22.     int n;
    
23.     printf("请输入楼梯的阶梯数: ");
    
24.     scanf("%d", &n);
    
25. 
    
26.     int result = climb_stairs(n);
    
27.     printf("一共有 %d 种方法到达楼顶。\n", result);
    
28. 
    
29.     return 0;
    
30. }
    

复制代码

跳转到最佳答案楼层

sfqxx

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

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

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

1. MOD = 100007
   
2. 
   
3. def climb_stairs(n):
   
4.     if n == 0 or n == 1:
   
5.         return 1
   
6.     if n == 2:
   
7.         return 2
   
8. 
   
9.     s = [0] * (n+1)
   
10.     s[0] = 1
    
11.     s[1] = 1
    
12.     s[2] = 2
    
13. 
    
14.     for i in range(3, n+1):
    
15.         s[i] = (s[i-1] + s[i-2]) % MOD
    
16. 
    
17.     return s[n]
    
18. 
    
19. # 测试样例
    
20. print(climb_stairs(3)) # 输出为 3

复制代码

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

isdkz

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

1. def climb_stairs(n):
   
2.     if n <= 2:
   
3.         return n
   
4. 
   
5.     dp = [0] * (n + 1)
   
6.     dp[1] = 1
   
7.     dp[2] = 2
   
8. 
   
9.     for i in range(3, n + 1):
   
10.         dp[i] = (dp[i - 1] + dp[i - 2]) % 100007
    
11. 
    
12.     return dp[n]
    
13. 
    
14. n = int(input("请输入楼梯的阶梯数: "))
    
15. result = climb_stairs(n)
    
16. print("一共有 %d 种方法到达楼顶。" % result)
    

复制代码

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

isdkz

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

这是C语言版本：

1. #include <stdio.h>
   
2. 
   
3. // 计算有多少种方法到达楼顶的函数
   
4. int climb_stairs(int n) {
   
5.     if (n <= 2) {
   
6.         return n;
   
7.     }
   
8. 
   
9.     int dp[n + 1]; // 定义动态规划数组
   
10.     dp[1] = 1;
    
11.     dp[2] = 2;
    
12. 
    
13.     // 从第3阶开始，计算到达每个阶梯的方法数
    
14.     for (int i = 3; i <= n; i++) {
    
15.         dp[i] = (dp[i - 1] + dp[i - 2]) % 100007; // 更新动态规划数组，取模100007防止整数溢出
    
16.     }
    
17. 
    
18.     return dp[n];
    
19. }
    
20. 
    
21. int main() {
    
22.     int n;
    
23.     printf("请输入楼梯的阶梯数: ");
    
24.     scanf("%d", &n);
    
25. 
    
26.     int result = climb_stairs(n);
    
27.     printf("一共有 %d 种方法到达楼顶。\n", result);
    
28. 
    
29.     return 0;
    
30. }
    

复制代码

isdkz

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

这是递归版本：

1. #include <stdio.h>
   
2. 
   
3. // 计算递归方法的函数
   
4. int climb_stairs_recursive(int n) {
   
5.     if (n == 1) {
   
6.         return 1;
   
7.     }
   
8.     if (n == 2) {
   
9.         return 2;
   
10.     }
    
11. 
    
12.     // 递归调用
    
13.     return (climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)) % 100007;
    
14. }
    
15. 
    
16. int main() {
    
17.     int n;
    
18.     printf("请输入楼梯的阶梯数: ");
    
19.     scanf("%d", &n);
    
20. 
    
21.     int result = climb_stairs_recursive(n);
    
22.     printf("一共有 %d 种方法到达楼顶。\n", result);
    
23. 
    
24.     return 0;
    
25. }
    

复制代码

白痴爱面包

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

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

isdkz

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

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

柿子饼同学

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int mod = 100007;
   
5. 
   
6. int climb(int stair){
   
7.     if(stair <= 1) return 1;
   
8.     // 递归边界, 小于 1 就只有一种方法了
   
9.     return (climb(stair - 1) + climb(stair - 2)) % mod;
   
10.     // 走到这个台阶的方法数是 stair-1 阶方法数 + stair-2 阶方法数
    
11. }
    
12. int n;
    
13. 
    
14. int main(){
    
15.     ios::sync_with_stdio(0);
    
16.     cin.tie(0);
    
17. 
    
18.     cin >> n;
    
19.     cout << climb(n);
    
20.    
    
21.     return 0;
    
22. }

复制代码