其實這題有不用 DP 的作法：

(1) 將棋盤拆成兩組獨立的對角線子棋盤，並皆旋轉 45 度為直橫方向

(2) 對於每個子棋盤，由格子數少的 row 開始填，那麼每次 (如果決定放置) 的可能數就是當前 row 的格子數減去已經放置的棋子數，

再與之前累計的方法數相乘就能再度累加進當前放置棋子數所對應到的方法數。

(3) 全部 k 個棋子，就可以拆成 (A子棋盤 0 個 * B子棋盤 k 個) + (A子棋盤 1 個 * B子棋盤 k-1 個) + (A子棋盤 2 個 * B子棋盤 k-2 個) + ... + (A子棋盤 k 個 * B子棋盤 0 個) 下去計算。

https://alan23273850.github.io/Online-Judge-Problems/zerojudge/a682-00861-Little-Bishops/

如果覺得這個方法讚的話請在下面留言，給我點鼓勵～～～