萨西摩尔·槿花 发表于 2022-9-24 10:57:00

经典问题之爬楼梯（c）

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

cnkizy 发表于 2022-9-24 11:32:39

像动态规划

zhangjinxuan 发表于 2022-9-24 12:25:01

本帖最后由 zhangjinxuan 于 2022-9-24 12:28 编辑

这是我的答案：

递推法，有点像斐波那契数列：
#include <cstdio>

using namespace std;

int n, k;

int get(int x) {
        if (x < 0)
                return 0;
        return x;
}

long long solve(int n) {
        long long dp = {1, 1};
        for (int i = 2; i <= n; ++i)
                for (int j = 1; j <= k; ++j)
                        dp += dp;
        return dp;
}
int main() {
        scanf("%d%d", &n, &k);
        printf("%lld", solve(n));
        return 0;
}

柿子饼同学 发表于 2022-9-24 12:30:44

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

高山 发表于 2022-9-24 13:56:37

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 100000 + 10;

int dp;
void solve()
{
      int n,k;
      scanf("%d%d",&n,&k);
      for(int i =1;i<=k;i++) dp = 1;
      for(int i = 2;i<=n;i++)
      {
                for(int j = 1;j<=k&&j<=i;j++)
                {
                        dp = (dp+dp)%100003;
                }
      }
      printf("%d\n",dp);
}

int main()
{
      solve();
      return 0;
}回答不易，望设最佳

傻眼貓咪 发表于 2022-9-25 10:33:23

本帖最后由 傻眼貓咪 于 2022-9-25 10:35 编辑

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

C++#include <iostream>
#include <map>

using std::map;
int foo(int n, int k, map <int, int> MAP) {
        int count = 0;
        if (not(n)) return 1;
        if (MAP.count(n)) return MAP;
        else if (n >= k) {
                for (int i = 1; i <= k; ++i) count += foo(n - i, k, MAP);
        }
        else count += foo(n, n, MAP);
        MAP = count;
        return count;
}

using std::cout, std::endl;
int main(void) {
        map <int, int> MAP;
        int n = 10, k = 4;
        cout << foo(n, k, MAP) << endl;
        return 0;
}Javaimport java.util.*;

public class Main
{
        public static int foo(int n, int k, Map <Integer, Integer> map) {
          int count = 0;
          if (n == 0) return 1;
          if (map.containsKey(n)) return map.get(n);
          else if (n >= k) {
                for (int i = 1; i <= k; ++i) count += foo(n - i, k, map);
          }
          else count += foo(n, n, map);
          map.put(n, count);
          return count;
        }
       
        public static void main(String[] args) {
          Map <Integer, Integer> map = new HashMap <Integer, Integer>();
          int n = 10, k = 4;
                System.out.println(foo(n, k, map));
        }
}Pythondef foo(n, k, MAP = dict()):
    count = 0
    if not n: return 1
    if n in MAP.keys(): return MAP
    elif n >= k:
      for i in range(1, k + 1):
            count += foo(n - i, k, MAP)
    else: count += foo(n, n, MAP)
    MAP = count
    return count

n, k = 10, 4
print(foo(n, k))

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

萨西摩尔·槿花 发表于 2022-9-28 15:57:07

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

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

zhangjinxuan 发表于 2022-9-28 18:21:09

我的代码没有通过吗?
页: [1]
查看完整版本: 经典问题之爬楼梯（c）