ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

2019-02-02

Educational DP Contest / DP まとめコンテスト H - Grid 1

解法

$dp[i][j] =$ マス $(i,j)$ に移動する方法数
とします。
すると、 $(i,j)$ に移動するには、 $(i-1,j)$ もしくは $(i,j-1)$ を通るしかないので、
$a_{i,j} = \#$ ならば $dp[i][j] =0$ 、
そうでなければ $dp[i][j] = dp[i-1][j] + dp[i][j-1]$
となります。
答えは $dp[h][w]$ を見ればわかります。