競プロ典型90問 050(★3) DP

050 - Stair Jump（★3）

問題

N 段の階段 があり、一歩で 1 段か L 段上がれる。

0 段目からN 段目までたどり着く移動方法何通りか、10⁹ + 7 で割った余りを求める。

解法

そこまでに行ける通り数をDPで下から計算する。

答えは大きくなるので常にmodを取りながら計算する。

最終的にDP[N]が答えとなる。

全体計算量はO(N)で解ける。

所感

DP は苦手なのでなかなか思いつかなかった。

DP 関連の資料は多いので、この解き方になれるようにしたい。

コード

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
const int INF = (int)1e9;
const ll INFL = (ll)1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
int dx[]={0, 0, -1, 1};
int dy[]={1, -1, 0, 0};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

ll dp[100100] = {};

int main()
{
    ll n, l;
    cin >> n >> l;

    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (i < l)
            dp[i] = dp[i - 1];
        else
            dp[i] = (dp[i - 1] + dp[i - l]) % MOD; // lより大きくなったら, i - l から上がってくる場合も考慮する
    }
    cout << dp[n] << endl;
    return 0;
}