https://atcoder.jp/contests/abc183/tasks/abc183_e
まず1次元で右にしか進めない場合を考える。 dp[i]=左からi番目に移動する方法 とする。
dp[i]=2^(n-1)である。1,…,i-1それぞれで立ち止まるか通過するか選べると考えてもいいが、dp[1]=1であり、i番目にいる時、移動をそこでやめてそこで立ち止まってi+1に進むか、そのまま移動してi+1に行くかの2通りがあるので、dp[i+1]=2*dp[i]であると考えられる。
2次元にすると、向きが変わる場合があるので
各マスでの状態を
- 右向きで進んでいる
- 下向きに進んでいる
- 斜め右下向きに進んでいる
- 立ち止まっている
という状態も含めて考える。 dp[1,1,1]=1,dp[1,1,k]=0 (k=1,2,3)で、
dp[i,j,1]=dp[i-1,j,1]+dp[i-1,j,4]
dp[i,j,2]=dp[i,-1j,2]+dp[i,j-1,4]
dp[i,j,3]=dp[i-1,j-1,3]+dp[i-1,j-1,4]
dp[i,j,4]=dp[i-1,j,1]+dp[i,j-1,2]+dp[i-1,j-1,3] + dp[i-1,j,4]+dp[i,j-1,4]+dp[i-1,j-1,4]
最後に(h,w)で着地する必要があるので、dp[h,w,4]が答えである。