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

萨西摩尔·槿花

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

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-9-25 10:33:23

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

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[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[n] = 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;
}

Java

import 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));
        }
}

Python

def foo(n, k, MAP = dict()):
    count = 0
    if not n: return 1
    if n in MAP.keys(): return MAP[n]
    elif n >= k:
        for i in range(1, k + 1):
            count += foo(n - i, k, MAP)
    else: count += foo(n, n, MAP)
    MAP[n] = count
    return count

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

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

跳转到最佳答案楼层

cnkizy

像动态规划

zhangjinxuan

这是我的答案：

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

#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[1000] = {1, 1};
        for (int i = 2; i <= n; ++i)
                for (int j = 1; j <= k; ++j)
                        dp[i] += dp[get(i - j)];
        return dp[n];
}
int main() {
        scanf("%d%d", &n, &k); 
        printf("%lld", solve(n));
        return 0;
}

柿子饼同学

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

高山

#include<bits/stdc++.h>

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

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

int main()
{
        solve();
        return 0;
}

回答不易，望设最佳

傻眼貓咪

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

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[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[n] = 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;
}

Java

import 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));
        }
}

Python

def foo(n, k, MAP = dict()):
    count = 0
    if not n: return 1
    if n in MAP.keys(): return MAP[n]
    elif n >= k:
        for i in range(1, k + 1):
            count += foo(n - i, k, MAP)
    else: count += foo(n, n, MAP)
    MAP[n] = count
    return count

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

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

萨西摩尔·槿花

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

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

zhangjinxuan

我的代码没有通过吗?