[已解决]经典问题之爬楼梯（c）

萨西摩尔·槿花

台阶数仍为n，每次你可以向上走至少1个至多 K 个台阶，有多少种不同走法？

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-9-25 10:33:23

纯粹想练习练习，太久没有写代码了，生疏
我的思路：动态规划

C++

1. #include <iostream>
   
2. #include <map>
   
3. 
   
4. using std::map;
   
5. int foo(int n, int k, map <int, int> MAP) {
   
6.         int count = 0;
   
7.         if (not(n)) return 1;
   
8.         if (MAP.count(n)) return MAP[n];
   
9.         else if (n >= k) {
   
10.                 for (int i = 1; i <= k; ++i) count += foo(n - i, k, MAP);
    
11.         }
    
12.         else count += foo(n, n, MAP);
    
13.         MAP[n] = count;
    
14.         return count;
    
15. }
    
16. 
    
17. using std::cout, std::endl;
    
18. int main(void) {
    
19.         map <int, int> MAP;
    
20.         int n = 10, k = 4;
    
21.         cout << foo(n, k, MAP) << endl;
    
22.         return 0;
    
23. }

复制代码

Java

1. import java.util.*;
   
2. 
   
3. public class Main
   
4. {
   
5.         public static int foo(int n, int k, Map <Integer, Integer> map) {
   
6.             int count = 0;
   
7.             if (n == 0) return 1;
   
8.             if (map.containsKey(n)) return map.get(n);
   
9.             else if (n >= k) {
   
10.                 for (int i = 1; i <= k; ++i) count += foo(n - i, k, map);
    
11.             }
    
12.             else count += foo(n, n, map);
    
13.             map.put(n, count);
    
14.             return count;
    
15.         }
    
16.        
    
17.         public static void main(String[] args) {
    
18.             Map <Integer, Integer> map = new HashMap <Integer, Integer>();
    
19.             int n = 10, k = 4;
    
20.                 System.out.println(foo(n, k, map));
    
21.         }
    
22. }

复制代码

Python

1. def foo(n, k, MAP = dict()):
   
2.     count = 0
   
3.     if not n: return 1
   
4.     if n in MAP.keys(): return MAP[n]
   
5.     elif n >= k:
   
6.         for i in range(1, k + 1):
   
7.             count += foo(n - i, k, MAP)
   
8.     else: count += foo(n, n, MAP)
   
9.     MAP[n] = count
   
10.     return count
    
11. 
    
12. n, k = 10, 4
    
13. print(foo(n, k))

复制代码

C 懒的写，就不写了 ，至於 C++ 速度极慢，参数如果太大需要时间运行。

跳转到最佳答案楼层

萨西摩尔·槿花

高山 发表于 2022-9-24 13:56
回答不易，望设最佳

您好，我是小白，请问输出dp是什么意思？dp不是一个数组吗