DP(動的計画法)

atcoder.jp

常に右隣との差の絶対値が1であるようなN桁の数列が何通りあるかという問題。(各桁1～9)

例えば
N=1の時は9通り。
N=2の時は、
であるから25通りとなる。

1桁目がyだった場合、x桁目は何通りあるかを表に表すと次のようになる。
N列目の合計が答えになる。
この表をdpで作る。

    // x = 1 の場合のみ初期化
    for (int i = 0; i < 9; ++i) {
        dp[i][0] = 1;
    }

    for (int x = 1; x < n; ++x) { // x　1桁目～n桁目
        for (int y = 0; y < 9; ++y) { // y　0～8
            if (y == 0) dp[y][x] = dp[y][x - 1] + dp[y + 1][x - 1];
            else if (y == 8) dp[y][x] = dp[y][x - 1] + dp[y - 1][x - 1];
            else dp[y][x] = dp[y - 1][x - 1] + dp[y][x - 1] + dp[y + 1][x - 1];           
        }
    }

    int ans = 0;
    for (int i = 0; i < 9; ++i) {
        ans += dp[i][n - 1];
    }
    cout << ans << endl;

ここで、問題文に998244353 で割った余りを求めてください。とあることに注意。
MODを求める問題では、処理中の足し算全てでMODを行ってOK。
全ての足し算でMODを求めると以下のようになる。

atcoder.jp