Mogu Mogu 2

解説

$(1,1)$ から $(H,W)$ までの経路は $\displaystyle \frac{(H+W)!}{H!W!}$ 通りより、これらを全探索するのは現実的ではありません。 よって、計算量を落とす工夫を考えます。

マス $(i,j)$ について、その上と左のマスにおけるそのマスまでの経路で食べることが出来るおにぎりの最大値が分かっていれば マス $(i,j)$ までの経路で食べることが出来るおにぎりの最大値も分かります。これを活用して全てのマスにおいてそのマスまでの経路で食べることが出来るおにぎりの最大値を求めることができれば良いです。

具体的には、以下のようなDPを考えます。

$DP[i][j] = (マス (i,j) までの経路で食べることが出来るおにぎりの最大値)$

このDPの推移は、以下のようになります。

$$DP[i][j] = \begin{cases} \max(DP[i-1][j],\ DP[i][j-1]) + 1 & (\text{if } S_{i,j} = \#) \\ \max(DP[i-1][j],\ DP[i][j-1]) & (\text{if } S_{i,j} = .) \end{cases}$$

答えは $DP[H][W]$ です。このDPの計算は $O(HW)$ より、本制約において十分実行時間制限に間に合います。