题解 P1192 【台阶问题】

黑不溜秋帅 · 2019-12-05 15:58:49 · 题解

一开始想到的是普通动态规划，和经典走台阶一样的套路，但是好像会很复杂，就把之前k个台阶走法的总数保存为一个sum，就是当前台阶的走法总数。

#include <bits/stdc++.h>
using namespace std;
int n,k;
const int mod=100003;
int a[100005];
int main(){
    cin >> n >> k;
    a[0] = a[1] = 1;
    int i = 0;
    int j = 1;
    int sum = 1;
    while(j <= n){
        sum %= mod;
        a[j] = sum;
        sum += a[j];
        if(j - i < k){
            j ++;
        }
        else if(j - i >= k){
            sum -= a[i];
            i ++;
            j ++;
        }
    }
    cout << (a[n] + mod) % mod;
}