牛客爬楼梯问题

lsmCC

1. #include  <stdio.h>
   
2. int res=0;
   
3. int func(int u)  
   
4. {
   
5.     if(u==15)
   
6.     {
   
7.          return res++;            
   
8.     }
   
9.     else if(u<15)
   
10.     {
    
11.         func(u+1);
    
12.         func(u+2);
    
13.         
    
14.     }
    
15.    
    
16. 
    
17. }
    
18. 
    
19. 
    
20. 
    
21. int main()
    
22. {
    
23.     printf("%d",func(0));
    
24.     return 0;
    
25.    
    
26. }

复制代码

题目链接：https://ac.nowcoder.com/acm/problem/214862
为什么编译错误，然后应该怎么改才能通过

isdkz

这段代码有两个问题：

1. 函数 func 声明为 int 类型但是没有返回值。因为函数体内没有 return 语句，所以编译器会报错。

2. 在 func 函数的递归调用中，没有使用返回值。递归调用 func(u+1) 和 func(u+2) 时，返回的值并没有被使用，这样就会导致计算结果不正确。

以下是修改后的代码：

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

复制代码

修改后的代码中， func 函数的返回类型改为 void ，并且在递归调用中对返回值进行了处理，将其加入到 res 变量中。最后在 main 函数中输出 res 的值即可。

陶远航

您的代码存在一些问题，导致编译错误。我将为您指出这些问题并提供修改后的代码。

1. func 函数没有返回值，但其返回类型为 int。当 u >= 15 时，应返回一个整数值。
2. res 变量应该是全局变量，以便在 func 函数中递增并在 main 函数中打印。

以下是修改后的代码：

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

复制代码

这个修改后的代码应该可以编译并运行。但是，我建议您使用动态规划来解决这个问题，以避免重复计算和提高效率。以下是使用动态规划的解决方案：

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

复制代码

这个解决方案使用了一个数组 dp 来存储已经计算过的结果，从而避免了重复计算。这将大大提高程序的运行效率。
请注意，本回答来自GPT-4
如果问题已经解决，请设置最佳答案