[已解决]经典问题之爬楼梯（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++ 速度极慢，参数如果太大需要时间运行。

跳转到最佳答案楼层

cnkizy

像动态规划

zhangjinxuan

这是我的答案：

递推法，有点像斐波那契数列：

1. #include <cstdio>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int n, k;
   
6. 
   
7. int get(int x) {
   
8.         if (x < 0)
   
9.                 return 0;
   
10.         return x;
    
11. }
    
12. 
    
13. long long solve(int n) {
    
14.         long long dp[1000] = {1, 1};
    
15.         for (int i = 2; i <= n; ++i)
    
16.                 for (int j = 1; j <= k; ++j)
    
17.                         dp[i] += dp[get(i - j)];
    
18.         return dp[n];
    
19. }
    
20. int main() {
    
21.         scanf("%d%d", &n, &k);
    
22.         printf("%lld", solve(n));
    
23.         return 0;
    
24. }

复制代码

柿子饼同学

设 f[i] 代表走到第 n 阶一共的走法数 , 显然 f[n] 就是答案
要到 f[i] , 必定是从前面 1 阶 , 前 2 阶... 前 n 阶走过来的
所以 f[i] = f[i-1] + f[i-2] + ... f[i-n]
这样一直递推就可以了  注意 f[1] = 1 的边界条件
数组要特判下标 , 不能越界

高山

1. #include<bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. typedef long long LL;
   
5. const int maxn = 100000 + 10;
   
6. 
   
7. int dp[maxn];
   
8. void solve()
   
9. {
   
10.         int n,k;
    
11.         scanf("%d%d",&n,&k);
    
12.         for(int i =1;i<=k;i++) dp[i] = 1;
    
13.         for(int i = 2;i<=n;i++)
    
14.         {
    
15.                 for(int j = 1;j<=k&&j<=i;j++)
    
16.                 {
    
17.                         dp[i] = (dp[i]+dp[i-j])%100003;
    
18.                 }
    
19.         }
    
20.         printf("%d\n",dp);
    
21. }
    
22. 
    
23. int main()
    
24. {
    
25.         solve();
    
26.         return 0;
    
27. }

复制代码

回答不易，望设最佳

傻眼貓咪

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

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不是一个数组吗

zhangjinxuan

我的代码没有通过吗?