Typical DP Contest F問題:準急

問題:http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp

解法:dp[n]を,「駅がnまでであるとした時、nで止まらないという条件のもとで題意の条件を満たす部分集合の数」とする。すると、まず求める答えはdp[N+1]とすれば良い。また、dp[1]=dp[N]=0となる。これは駅1と駅Nはかならず止まるルールだからである。またdp[n]を考えるときにdp[n-k]というのは、「n-kが止まらなかった一番最近の駅でありかつn-kまでK駅連続で止まることがなかった場合の数」ということになる。よって、dp[n]=dp[n-1]+dp[n-2]+...dp[n-K+1]となる。これはdp[0]〜dp[n]までの合計sum[n]を保持しておけばO(1)で求めることができる。
答えを見ながら解いたのでなんとも言えないが、発想としてはまず「止まらない駅の部分集合のうち条件を満たすものがが何通りあるか？」ということを考えて、これには以下のような良い性質があるのでそれを利用するという感じ？
性質:上に書いたように、最後に止まった駅がわかればそれのみを用いてそれより後ろの状態を決定できる。
以下ソースコード

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)n; i++)

using namespace std;
typedef long long ll;

const int MAXN = 1000010;
const ll MOD = 1e9+7;
ll dp[MAXN]; // dp[n]: 駅nに止まらないという条件のもとで条件を満たす止まり方
ll sum[MAXN];

int main(void) {
    int N, K;
    cin >> N >> K;
    dp[0] = sum[1] = 1;
    for (int i = 1; i <= N+1; i++) {
        if (i != 1 && i != N) dp[i] = (sum[i]-sum[max(i-K,0)]+MOD) % MOD;
        sum[i+1] = (sum[i]+dp[i]) % MOD;
    }
    cout << dp[N+1] << endl;
    return 0;
}