当背景是高维，且状态与多个点相关时如何设计状态和正确转移？

比如：在 $N* M$ 棋盘上放棋子两两不相邻，问有多少种放法。
假定按从上到下从左到右的方式放：
位置 $(x,y)$ 能放当且仅当 $(x-1,y),(x,y-1)$ 都不放。
但是直接两个位置的方案相乘是不对的，因为可能产生重复。
网上解法只有状压，但是直觉是有多项式复杂度的做法的。

即，多维背景下的dp难以不重不漏的计数。