台阶问题

洛谷 P1192 台阶问题

题目链接:https://www.luogu.com.cn/problem/P1192

题目描述:

有N级的台阶,你一开始在底部,每次可以向上迈最多K级台阶(最少1级),问到达第N级台阶有多少种不同方式。

输入

两个整数

输出

一个正整数,为不同方式数,由于答案可能很大,你需要输出ans mod 100003后的结果。

样例

样例

思路:

某一阶的方案数,是相对当前位置的前k阶的每一阶的方案数的和。

代码:

#include<iostream>
#include<stdio.h>
using namespace std;
const int maxn=1e5+5;
const int m=1e5+3;
int dp[maxn];

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    dp[0]=1;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=k&&i-j>=0;j++){
            dp[i]+=dp[i-j];
            dp[i]%=m;
        }

    }
    printf("%d\n",dp[n]);
    return 0;
}
Last modification:December 10th, 2019 at 12:24 am
如果觉得我的文章对你有用,请随意赞赏