POJ 3493 Chessboard Puzzle

題目是說, 給出一個 n*n 的 grid, 每格有一個分數 (可以負), 現在要將每格染成白色或黑色, 總分計算的方法是:
----如果兩格相鄰而且異色, 把它們分數的乘積加到總分
問最大可能總分, n <= 16

---

做法是使用狀態DP
一開始是想用像炮兵陣地的方法DP, 即state是記一行的permutation, 但單是做一次transfer便要2²ⁿ了

後來聽超超說,
有一個很強的加速

考慮到每一格是黑/白最「遠」也只是影響到下面那格 (假設順序是一行行由左至右)
即 n 格後
可以順著做而且只記著前n步的狀態

即

......
......
......
......
......
......

做到紅色那格時, 只用記著藍色的排列, 每次transfer後只是把排列shift後一格 ->

......
......
......
......
......
......

把time complexity降至O(n²*2ⁿ)