JOI難易度６ 通勤経路

問題原文

atcoder.jp

問題要旨

縦 マス、横 マスのグリッドがある。
左上からスタートして、右か下への移動を繰り返して一番右下のマスを目指す。
曲がった直後に曲がることはできない という制約があるとき、一番右下のマスへたどりつく通り数はいくつあるか？

• 

解法

DP。ただ状態数がちょっと多い。
「直前に縦に曲がった」「直前に横に曲がった」「直前に縦にそのまま進んだ」「直前に横にそのまま進んだ」の４通りの状態が各マスについてある。
遷移は難しくないので丁寧にやる。

実装

一番左上のマスから始めると最初の１歩が面倒なので、１手進んだ状態からやると楽だと思う。（最初の移動は曲がったことにならないので）

W, H = map(int, input().split())
MOD = 10 ** 5

# dp0[w][h][k] := (w, h)にたどり着く通り数
# 直前に k: 0 曲がっておらず横に移動, k: 1 曲がっておらず縦に移動, k: 2 横に曲がった, k: 3 縦に曲がった
dp = [[[0] * 4 for _ in range(H)] for _ in range(W)]
dp[1][0][0] = 1
dp[0][1][1] = 1

for w in range(W):
    for h in range(H):
        if w + 1 < W:
            dp[w + 1][h][0] += dp[w][h][0]
            dp[w + 1][h][0] += dp[w][h][2]

            dp[w + 1][h][2] += dp[w][h][1]

        if h + 1 < H:
            dp[w][h + 1][1] += dp[w][h][1]
            dp[w][h + 1][1] += dp[w][h][3]

            dp[w][h + 1][3] += dp[w][h][0]


print(sum(dp[-1][-1]) % MOD)

感想

このDPがさくっとかけたのは素直に嬉しい。
前はナップサックDPすら満足にかけなかったからなぁ。。。