分析：对于小于等于k的数，每次可以由底部直接到达，一直到i-1直接到达；而对于大于k的数，每次由i-k个一直到i-1个直接到达
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=100010; 15 const int mod=100003; 16 int a[maxn]; 17 int dp[maxn]; 18 int n,k; 19 int main() 20 { 21 while(cin>>n>>k) 22 { 23 memset(dp,0,sizeof(dp)); 24 for(int i=1;i<=n;i++){ 25 for(int j=1;j<=k;j++) 26 { 27 if(i<=j){ 28 ++dp[i]; break; 29 } 30 else 31 dp[i]=(dp[i]+dp[i-j])%mod; 32 } 33 } 34 cout<<dp[n]<<endl; 35 } 36 return 0; 37 }