动态规划 上楼梯问题

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

题目描述

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

输入格式

两个正整数N，K。

输出格式

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

输入

5 2

输出

8

说明/提示 对于20 %的数据,有N ≤ 10, K ≤ 3N≤10,K≤3;

对于40@%的数据，有N ≤ 1000N≤1000;

对于1000%的数据，有N ≤ 100000,K ≤ 100N≤100000,K≤100

初始化f[0]=1则是在后面递推的时候写着方便，f[0]的意义在于，由于我们枚举了j=min(i,k),即可能存在i==j的情况，具体意义为一步迈到终点（条件为i<=k），这一步是合法方案，所以令f[0]=1让计算一般化；

#include <iostream> using namespace std; int dp[100]={1,1}; int main(int argc, char const *argv[]) { int n,k; cin>>n>>k; for(int i=2;i<=n;i++) { for(int t=1;t<=min(i,k);t++) { dp[i]=dp[i]+dp[i-t]%10003; } } cout<<dp[n]<<endl; return 0; }