POJ 3254 Corn Fields

問題

http://poj.org/problem?id=3254

n*mのグリッドが与えられる。各要素は0または1であり、1のグリッドには物を置くことが出来る。隣接した二つのマスにものを置いてはいけないという制約下で、何通りの置き方があるかを答える問題。

解法

dp[i][bit] = i列目を状態bitで置いた時の置き方の場合の数

とするとO(2^(n+m))で解ける。

最初は0も連続してはいけないと勘違いしてて変なこと書いてた。