編程之美的課後題也有一個和整個題目一樣的。（P269)
題目
這個題目的題意很容易理解，在一個N*M的格子裡，我們現在有兩種類型的磚塊，1 * 2和 2 * 1，問一共有多少種方案，可以將整個N*M的空間都填滿。
最簡單的例子就是下面的了：
編程之美中題目：
某年夏天,位於希格瑪大廈四層的微軟亞洲研究院對辦公樓的天井進行了一次大規模的裝修.原來的地板鋪有 N×M 塊正方形瓷磚,這些瓷磚都已經破損老化了,需要予以更新.裝修工人們在前往商店選購新的瓷磚時,發現商店目前只供應長方形的瓷磚,現在的一塊長方形瓷磚相當於原來的兩塊正方形瓷磚,工人們拿不定主意該買多少了,讀者朋友們請幫忙分析一下:能否用1×2的瓷磚去覆蓋 N×M 的地板呢?
下面我們來分析：
這個題目類屬於狀態壓縮DP，對於狀態壓縮DP，其實最簡單的理解就是把狀態用比特位的形式表示出來，我們會在下面用例子來說明。
假如現在我們在鋪磚 位置(i,j), 並且假設之前的位置已經鋪設好的了，在這個位置，我們的選擇：
1. 不用鋪磚了，可能在(i-1, j)的時刻已經被豎著鋪上了，然後考慮的是（i， j+1）
2. 橫鋪磚，將(i, j+1）也鋪上了，然後考慮的是(i, j+2)。
3. 豎著鋪磚，（將i，j）和（i+1，j）鋪上一個豎立的轉頭。
所以我們如下翻譯我們的選擇，在位置(i, j) 如果我們選擇橫著貼磚，那麼將(i, j), (i, j+1)都填寫成1，如果豎著貼磚，我們將(i,j)填寫成0，將(i+1, j)填寫成1.
問題1：為什麼要這麼計數呢，我覺得應該這樣理解：
1. 在橫著貼磚的時候，(i, j), (i, j+1) 都是1，這個值其實對下一行如何選擇沒有影響。
2. 豎著貼磚的第二個，我們也選擇了1， 因為這個磚頭結束了，對下一行如何選擇依然沒有影響。
3. 而豎著的第一個磚頭，這個磚頭是對下面有影響的，如果(i,j)是0，那麼(i+1,j)只有是1的情況下才能滿足條件。
即當設為1表示對下一行沒有任何影響了。
問題2：如何判斷當前狀態與上一行的狀態是否兼容
其實我們在上面已經基本給出分析， 如果我們現在鋪設 (i,x) x這裡表示第i行，第x列
1. 如果值 i 行，j 在x位上的值是0， 那麼第 i-1行，j的值在x位上一定是1。因為不可能在同一列相鄰的位置鋪兩個豎著的 第一個，如果滿足下一步測試的是(i, x+1), 否則直接返回不兼容。
2. 如果值 i 行，j在x位置的值是1 .
{
那麼有可能有兩種情況：
1. (i-1, x)是0， 這個時候一定是豎著鋪設了，下一步檢測的是(i, x + 1)
2. (i-1, x) 是1， 如果是這樣的話，那麼(i, x)一定是要選擇橫著鋪了，那麼(i,x+1)也一定是1，並且(i-1,x + 1)一定是1（如果是0，就是豎著鋪了），如果不滿足就返回不兼容，滿足條件 就測試(i,x + 2)
圖片
}
對於第一行的兼容性，我們要做一下特別的分析，在第一行中，要麼放0， 要麼放1。
加入當前測試的是 DP(0, j)的第 x的比特位，即第0行，x列
1. 如果x是1，那麼 x + 1 也一定是1，然後測試到 x + 2
2. 如果x是0， 那麼直接測試下一個 x + 1
特別注意：這裡的判斷的(i,x)一定不是由(i,x-1)位橫著鋪磚過來的，否則直接x=x+2,就不會來判斷(i,x)位了。
問題3：為什麼可以使用動態規劃算法來解決這個問題？
這就得從動態規劃的特性上去找：
(1)最優子結構
用F[i][j]表示第i行j狀態鋪磚塊的方案數，一定等於i-1行所有的能與狀態j兼容的狀態k的方案的總和。
(2)重復子問題
求F[i][j]即第i行的每一個狀態一定要用到第i-1行的各個狀態。
問題4：從狀態壓縮的特點來看，這個算法適用的題目符合以下的條件：
1.解法需要保存一定的狀態數據（表示一種狀態的一個數據值），每個狀態數據通常情況下是可以通過二進制來表示的。這就要求狀態數據的每個單元只有兩種狀態，比如說棋盤上的格子，放棋子或者不放，或者是硬幣的正反兩面。這樣用 0 或者 1 來表示狀態數據的每個單元，而整個狀態數據就是一個一串 0 和 1 組成的二進制數。
2.解法需要將狀態數據實現為一個基本數據類型，比如 int， long等等，即所謂的狀態壓縮。狀態壓縮的目的一方面是縮小了數據存儲的空間，另一方面是在狀態對比和狀態整體處理時能夠提高效率。這樣就要求狀態數據中的單元個數不能太大，比如用 int 來表示一個狀態的時候，狀態的單元個數不能超過 32（32 位的機器）。
代碼：
