AscNumber(Easy) [yukicoder No.741]

前提知識

• 桁DP

解法

https://yukicoder.me/submissions/289853

この問題はN桁以下の数でAscNumberである数の個数を求めている。
　
桁DPをする。
DP[dgt][lst] := dgt桁まで確定していて最下位の桁の数がlstである組み合わせ
これは簡単な桁DPなので、実装する。

int N;
mint dp[1010101][10];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    rep(i, 0, 10) dp[1][i] = 1;
    rep(i, 1, N) rep(lst, 0, 10) {
        rep(nxt, lst, 10) dp[i + 1][nxt] += dp[i][lst];
    }
    
    mint ans = 0;
    rep(lst, 0, 10) ans += dp[N][lst];
    cout << ans << endl;
}