POJ 2411 Mondriaan's Dream

想法：

狀態壓縮DP，我們定義一列(橫的)一個狀態D：

• 第i位置為1表示這一列位置i和下一列位置i是由直長方形組成(|)
• 第i位置為0表示1以外的情況

注意以上的定義，以這題題目的圖來看，

• 第一列狀態D1=(00100001100)2
• 第二列狀態D2=(11010010000)2
• 第三列狀態D3=(00100001001)2
• 其他列依此類推，最後一列一定全部都是0。

接下來定義dp[i][d] = k，表示第i列在狀態d的情況下有k個方法數。如果能接受的話，那麼根據定義，如果第H列是圖的最後一列，本題答案就是dp[H][0]。

    定義完成後，基本上的做法是從最上面那列開始往下更新，例如第i列狀態a如果能和第i+1列狀態b相鄰(注意任兩個狀態不一定相鄰..)，那麼dp[i+1][b]+=dp[i][a];，就這樣枚舉所有狀態，最後輸出答案dp[H][0]。

    為了簡化code，不用初始化第一列每個狀態方法數是1(因為第一列所有狀態都是可以的)，因此我們直接初始化dp[0][0]=1，令這個假設的第0列狀態0方法數為1。

    另外在做以上的for loop之前，先建個狀態是否可以相鄰的表，令adjacent[i][j] = true表示狀態i在這列而狀態j在下一列是可以相鄰的，如最上面題目example，adjacent[D1][D2]==true，adjacent[D2][D3]==true。

    最後總結一下，為了加速，我們可以總是讓寬比較小高比較大，這樣可以減少每列的狀態數，另外也能用個ans[H][W]來紀錄答案，如果重複的題目就直接輸出即可。