[已解决]爬楼梯

bangbang-ande

题目是这样子的：

题目描述
楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式
一个数字，楼梯数。

输出格式
输出走的方式总数。

输入输出样例
输入 #1
4
输出 #1
5
说明/提示
对于 60\%60% 的数据，N≤50；
对于 100\%100% 的数据，N≤5000。

然后写的代码是这样的：

1. #include <stdio.h>
   
2. 
   
3. int ans = 0;
   
4. 
   
5. int f(int n){
   
6.     if(n == 1){
   
7.         ans += 1;
   
8.         return 0;
   
9.     }
   
10.     if(n == 2){
    
11.         ans += 2;
    
12.         return 0;
    
13.     }
    
14.     f(n - 1);
    
15.     f(n - 2);
    
16. }
    
17. 
    
18. int main(){
    
19.     int n;
    
20.     scanf("%d", &n);
    
21.     f(n);
    
22.     printf("%d", ans);
    
23. }

复制代码

可是运行起来是四个通过，剩下的超了时间（时间复杂度1s， 空间复杂度125mb）
然后又改了一下：

1. #include <stdio.h>
   
2. 
   
3. int ans = 0;
   
4. 
   
5. int f(int n){
   
6.     if(n == 1 && n == 2){
   
7.         ans += 1;
   
8.         return 0;
   
9.     }
   
10.     f(n - 1);
    
11.     f(n - 2);
    
12. }
    
13. 
    
14. int main(){
    
15.     int n;
    
16.     scanf("%d", &n);
    
17.     f(n - 1);
    
18.     printf("%d", ans);
    
19. }

复制代码

结果空间复杂度又出问题。。。
请问还有没有更好的方法？

可以来下边那个网站测试
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
题目网站：https://www.luogu.com.cn/problem/P1255

最佳答案

月排行榜 / 总排行榜

Junpei

2020-8-4 17:24:16

从我的力扣代码改的，这5000这种数据太大了，还得写个字符串表示大整数的加法，用动态规划从底层遍历到顶层结果就出来了

1. #include<iostream>
   
2. #include<vector>
   
3. #include<string>
   
4. 
   
5. using namespace std;
   
6. 
   
7. vector<string> vec(5001, "0");
   
8. 
   
9. string addStrings(string num1, string num2) //字符串加法:"1"+"1"="2"
   
10. {
    
11.         num1 = '0' + num1;
    
12.         num2 = '0' + num2;
    
13.         int len1 = num1.size();
    
14.         int len2 = num2.size();
    
15. 
    
16.         string ans = "";
    
17.         int cry = 0;
    
18.         len1--;
    
19.         len2--;
    
20.         char ch;
    
21.         while (len1 != -1 && len2 != -1)
    
22.         {
    
23.                 ch = num1[len1] + num2[len2] + cry - '0';
    
24.                 if (ch > '9')
    
25.                 {
    
26.                         ans = (char)(ch - 10) + ans;
    
27.                         cry = 1;
    
28.                 }
    
29.                 else
    
30.                 {
    
31.                         ans = ch + ans;
    
32.                         cry = 0;
    
33.                 }
    
34.                 len1--;
    
35.                 len2--;
    
36.         }
    
37. 
    
38.         if (len1 == -1)
    
39.                 while (len2 > -1)
    
40.                 {
    
41.                         ch = num2[len2] + cry;
    
42.                         if (ch > '9')
    
43.                         {
    
44.                                 ans = (char)(ch - 10) + ans;
    
45.                                 cry = 1;
    
46.                         }
    
47.                         else
    
48.                         {
    
49.                                 ans = ch + ans;
    
50.                                 cry = 0;
    
51.                         }
    
52.                         len2--;
    
53.                 }
    
54.         else
    
55.                 while (len1 > -1)
    
56.                 {
    
57.                         ch = num1[len1] + cry;
    
58.                         if (ch > '9')
    
59.                         {
    
60.                                 ans = (char)(ch - 10) + ans;
    
61.                                 cry = 1;
    
62.                         }
    
63.                         else
    
64.                         {
    
65.                                 ans = ch + ans;
    
66.                                 cry = 0;
    
67.                         }
    
68.                         len1--;
    
69.                 }
    
70. 
    
71.         if (ans[0] == '0')
    
72.                 ans = ans.substr(1);
    
73. 
    
74.         return ans;
    
75. }
    
76. 
    
77. string  climbStairs(int n)
    
78. {
    
79.         vec[1] = "1";
    
80.         vec[2] = "2";
    
81. 
    
82.         if (n == 1)
    
83.                 return "1";
    
84.         if (n == 2)
    
85.                 return "2";
    
86. 
    
87.         for (int i = 3; i <= n; i++)
    
88.                 vec[i] = addStrings(vec[i - 1], vec[i - 2]);
    
89. 
    
90.         return vec[n];
    
91. }
    
92. 
    
93. int main()
    
94. {
    
95.     ios::sync_with_stdio(false);
    
96.     int num;
    
97.     cin >> num;
    
98.     string ans = climbStairs(num);
    
99.     cout << ans;
    
100. 
     
101.     return 0;
     
102. }
     

复制代码

跳转到最佳答案楼层

Seawolf

1. public int climbStairs(int n) {
   
2.     // base cases
   
3.     if(n <= 0) return 0;
   
4.     if(n == 1) return 1;
   
5.     if(n == 2) return 2;
   
6.    
   
7.     int one_step_before = 2;
   
8.     int two_steps_before = 1;
   
9.     int all_ways = 0;
   
10.    
    
11.     for(int i=2; i<n; i++){
    
12.         all_ways = one_step_before + two_steps_before;
    
13.         two_steps_before = one_step_before;
    
14.         one_step_before = all_ways;
    
15.     }
    
16.     return all_ways;
    
17. }

复制代码

xiaosi4081

你应该不是时间复杂度出问题，是最后忘了return了（结果报错了），还有你这个f函数不用返回值呀

1. #include <stdio.h>
   
2. 
   
3. int ans = 0;
   
4. void f(int n){
   
5.    
   
6.     if(n == 1 && n == 2){
   
7.         ans += 1;
   
8.         return;
   
9.     }
   
10.     f(n - 1);
    
11.     f(n - 2);
    
12.     return;
    
13. }
    
14. 
    
15. int main(){
    
16.     int n;
    
17.     scanf("%d", &n);
    
18.     f(n - 1);
    
19.     printf("%d", ans);
    
20. }

复制代码

bangbang-ande

xiaosi4081 发表于 2020-7-29 13:46
你应该不是时间复杂度出问题，是最后忘了return了（结果报错了），还有你这个f函数不用返回值呀

但是还是不对啊

xiaosi4081

bangbang-ande 发表于 2020-7-29 15:11
但是还是不对啊

发错的内容（不要任何改动）

Unicorn#

递归函数执行次数太多了，改成递推就好了
另外，头像好评

1. int climbStairs(int n){
   
2.     int a=1, b=1;
   
3.     for(int i = 1; i < n; i++)
   
4.     {
   
5.         b += a;
   
6.         a = b - a;
   
7.     }
   
8.     return b;
   
9. }

复制代码

405794672

有大佬告诉我60\%60%是什么意思吗？

bangbang-ande

题目网站：https://www.luogu.com.cn/problem/P1255

风过无痕1989

Seawolf 发表于 2020-7-29 13:04

请教：你这是 VC++ 程序吗？我用 VC++6.0 没通过。谢谢!

bangbang-ande

风过无痕1989 发表于 2020-7-29 20:23
请教：你这是 VC++ 程序吗？我用 VC++6.0 没通过。谢谢!

是c程序

风过无痕1989

bangbang-ande 发表于 2020-7-29 20:31
是c程序

不是问你，你的程序当然是C程序啦

Seawolf

风过无痕1989 发表于 2020-7-29 20:23
请教：你这是 VC++ 程序吗？我用 VC++6.0 没通过。谢谢!

java

SHRS23

动态规划题目
leetcode测试通过
运行时间0 ms
内存消耗        5.2 MB

1. int climbStairs(int n)
   
2. {
   
3.     int dp[n+3];
   
4.     int i;
   
5.    
   
6.     dp[0]=0;
   
7.     dp[1]=1;
   
8.     dp[2]=2;
   
9.    
   
10.     for(i=3;i<=n;i++)
    
11.     {
    
12.         dp[i]=dp[i-1]+dp[i-2];
    
13.     }
    
14.     return dp[n];
    
15. }

复制代码

bangbang-ande

SHRS23 发表于 2020-7-29 22:38
动态规划题目
leetcode测试通过
运行时间0 ms

你可不可以试试这个测试网站：
https://www.luogu.com.cn/problem/P1255

Cool_Breeze

1. #include <stdio.h>
   
2. #define size_t long long
   
3. 
   
4. int main()
   
5. {
   
6.         size_t n=0;
   
7.         scanf("%d",&n);
   
8.         register size_t f1=1;
   
9.         register size_t f2=1;
   
10.         if (n == 1 || n == 2 || n == 3)
    
11.         {
    
12.                 printf("%d", n);
    
13.                 return 0;
    
14.         }
    
15.         else
    
16.         {
    
17.                 for(int i = 3;i < n;i++)
    
18.                 {
    
19.                         f1=f1+f2;
    
20.                         f2=f2+f1;
    
21.                 }
    
22.         }
    
23.         printf("%d", f1 + f2);
    
24.         return 0;
    
25. }

复制代码

SHRS23

bangbang-ande 发表于 2020-7-29 23:18
你可不可以试试这个测试网站：
https://www.luogu.com.cn/problem/P1255

抱歉我没有洛谷账号

SHRS23

1. #include<stdio.h>
   
2. 
   
3. int climbStairs(int n)
   
4. {
   
5.     long long dp[n+3];
   
6.     int i;
   
7.    
   
8.     dp[0]=0;
   
9.     dp[1]=1;
   
10.     dp[2]=2;
    
11.    
    
12.     for(i=3;i<=n;i++)
    
13.     {
    
14.         dp[i]=dp[i-1]+dp[i-2];
    
15.     }
    
16.     return dp[n];
    
17. }
    
18. 
    
19. int main()
    
20. {
    
21.     int n = 0;
    
22.     scanf("%d",&n);
    
23.     printf("%ld", climbStairs(n));
    
24.     return 0;
    
25. }

复制代码

注册试了一下发现我竟然三年前注册过。。。
这是WA50的程序，不想改了，洛谷这数据大的离谱，我看题解大家都高精加法做的。。。

Junpei

从我的力扣代码改的，这5000这种数据太大了，还得写个字符串表示大整数的加法，用动态规划从底层遍历到顶层结果就出来了

1. #include<iostream>
   
2. #include<vector>
   
3. #include<string>
   
4. 
   
5. using namespace std;
   
6. 
   
7. vector<string> vec(5001, "0");
   
8. 
   
9. string addStrings(string num1, string num2) //字符串加法:"1"+"1"="2"
   
10. {
    
11.         num1 = '0' + num1;
    
12.         num2 = '0' + num2;
    
13.         int len1 = num1.size();
    
14.         int len2 = num2.size();
    
15. 
    
16.         string ans = "";
    
17.         int cry = 0;
    
18.         len1--;
    
19.         len2--;
    
20.         char ch;
    
21.         while (len1 != -1 && len2 != -1)
    
22.         {
    
23.                 ch = num1[len1] + num2[len2] + cry - '0';
    
24.                 if (ch > '9')
    
25.                 {
    
26.                         ans = (char)(ch - 10) + ans;
    
27.                         cry = 1;
    
28.                 }
    
29.                 else
    
30.                 {
    
31.                         ans = ch + ans;
    
32.                         cry = 0;
    
33.                 }
    
34.                 len1--;
    
35.                 len2--;
    
36.         }
    
37. 
    
38.         if (len1 == -1)
    
39.                 while (len2 > -1)
    
40.                 {
    
41.                         ch = num2[len2] + cry;
    
42.                         if (ch > '9')
    
43.                         {
    
44.                                 ans = (char)(ch - 10) + ans;
    
45.                                 cry = 1;
    
46.                         }
    
47.                         else
    
48.                         {
    
49.                                 ans = ch + ans;
    
50.                                 cry = 0;
    
51.                         }
    
52.                         len2--;
    
53.                 }
    
54.         else
    
55.                 while (len1 > -1)
    
56.                 {
    
57.                         ch = num1[len1] + cry;
    
58.                         if (ch > '9')
    
59.                         {
    
60.                                 ans = (char)(ch - 10) + ans;
    
61.                                 cry = 1;
    
62.                         }
    
63.                         else
    
64.                         {
    
65.                                 ans = ch + ans;
    
66.                                 cry = 0;
    
67.                         }
    
68.                         len1--;
    
69.                 }
    
70. 
    
71.         if (ans[0] == '0')
    
72.                 ans = ans.substr(1);
    
73. 
    
74.         return ans;
    
75. }
    
76. 
    
77. string  climbStairs(int n)
    
78. {
    
79.         vec[1] = "1";
    
80.         vec[2] = "2";
    
81. 
    
82.         if (n == 1)
    
83.                 return "1";
    
84.         if (n == 2)
    
85.                 return "2";
    
86. 
    
87.         for (int i = 3; i <= n; i++)
    
88.                 vec[i] = addStrings(vec[i - 1], vec[i - 2]);
    
89. 
    
90.         return vec[n];
    
91. }
    
92. 
    
93. int main()
    
94. {
    
95.     ios::sync_with_stdio(false);
    
96.     int num;
    
97.     cin >> num;
    
98.     string ans = climbStairs(num);
    
99.     cout << ans;
    
100. 
     
101.     return 0;
     
102. }
     

复制代码