元の問題は、あるマスを黒く塗った時その「下と右下」を黒く塗るというものでしたが、これを「下と右」に変えた問題を考えてみます。

変更後の問題は

\(dp[i][j]=\) \(i\) 行目まで塗り方を決めて、美しいグリッドであり、マス \((i,j)\) を白く、マス \((i,j+1)\) を黒く塗るようなものの個数

として、

\(dp[i][j]=\sum_{k\geq j} dp[i-1][k]\)

のようなDPにより解くことができます。これは累積和をとりながらDPすることで \(O(NM)\) で求めることができます。

元の問題もほとんど同様に解くことができます。

与えられたグリッドを、左上角を下に押し込むように、次のように斜めに変形します

#...#
.....
.....
.....
#....

  ↓

    #
   ..
  ...
 ....
#....
....
...
..
#

こうすると「下と右下」という条件は「下と右」という条件になるため、先に述べた問題と全く同じようにして解くことができます。