带说明的题解

/*
本题是走两步台阶的扩展，解题方法类似走两步台阶。分两个步骤：

1. 当 i <= k 时，走法是前面所有台阶走法之和 + 1。例如： k = 5，
   i = 4 时， a[4] = a[3] + a[2] + a[1] + 1。加一是因为缺少从0 一步
   走到 i 的走法。
2. 当 i > k 时，走法是前面 k 个台阶走法之和。
   */

#include<bits/stdc++.h>
using namespace std;
int main() {

  int n, k, a[105] = {};  // a 存放第 i 个台阶的走法
  int sum[105] = {};      // sum 存放前 i 个台阶的走法之和
  cin >> n >> k;
  a[1] = 1, sum[1] = 1;   // 初始条件
  for (int i = 2; i <= k; i++) {  // i <= k 时的走法
	  a[i] = sum[i-1] + 1;   
	  sum[i] = sum[i-1] + a[i];
  }
  for (int i = k + 1; i <= n; i++) {  // i > k 时的走法
	  a[i] = (sum[i-1]  - sum[i-1-k]) % 100003;
	  sum[i] = sum[i-1] + a[i];
  }
  cout << a[n];
  return 0;

}