## 本章動態規劃的習題 ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.10.md#1子序列個數)1.子序列個數 子序列的定義：對于一個序列a=a[1],a[2],......a[n]，則非空序列a'=a[p1],a[p2]......a[pm]為a的一個子序列 其中1<=p1<p2<.....<pm<=n。 例如：4,14,2,3和14,1,2,3都為4,13,14,1,2,3的子序列。 * 對于給出序列a，有些子序列可能是相同的，這里只算做1個。 * 要求輸出a的不同子序列的數量。 ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.10.md#2數塔取數問題)2.數塔取數問題 一個高度為N的由正整數組成的三角形，從上走到下，求經過的數字和的最大值。 每次只能走到下一層相鄰的數上，例如從第3層的6向下走，只能走到第4層的2或9上。 5 8 4 3 6 9 7 2 9 5 例子中的最優方案是：5 + 8 + 6 + 9 = 28。 ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.10.md#3最長公共子序列)3.最長公共子序列 什么是最長公共子序列呢?好比一個數列 S，如果分別是兩個或多個已知數列的子序列，且是所有符合此條件序列中最長的，則S 稱為已知序列的最長公共子序列。 舉個例子，如：有兩條隨機序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，則它們的最長公共子序列便是：4 5 5。 提示：最容易想到的算法是窮舉搜索法，但考慮到最長公共子序列問題也有最優子結構性質，可以用動態規劃解決。 ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.10.md#4最長遞增子序列)4.最長遞增子序列 給定一個長度為N的數組a0,a1,a2...,an-1，找出一個最長的單調遞增子序列（注：遞增的意思是對于任意的i<j，都滿足ai<aj，此外子序列的意思是不要求連續，順序不亂即可）。例如：給定一個長度為6的數組A{5， 6， 7， 1， 2， 8}，則其最長的單調遞增子序列為{5，6，7，8}，長度為4。 提示：一種解法是轉換為最長公共子序列問題，另外一種解法則是動態規劃。當我們考慮動態規劃解決時，可以定義dp[i]為以ai為末尾的最長遞增子序列的長度，故以ai結尾的遞增子序列 * 要么是只包含ai的子序列 * 要么是在滿足j<i并且aj<ai的以ai為結尾的遞增子序列末尾，追加上ai后得到的子序列 如此，便可建立遞推關系，在O(N^2)時間內解決這個問題。 ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.10.md#5木塊砌墻)5.木塊砌墻 用 1×1×1, 1×2×1以及2×1×1的三種木塊（橫綠豎藍，且綠藍長度均為2）， [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/32~33/33.1.png) 搭建高長寬分別為K × 2^N × 1的墻，不能翻轉、旋轉（其中，0<=N<=1024，1<=K<=4） [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/32~33/33.2.png) 有多少種方案，輸出結果 對1000000007取模。 舉個例子如給定高度和長度：N=1 K=2，則答案是7，即有7種搭法，如下圖所示： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/32~33/33.3.png) 提示：此題很有意思，涉及的知識點也比較多，包括動態規劃，快速矩陣冪，狀態壓縮，排列組合等等都一一考察了個遍。 而且跟一個比較經典的矩陣乘法問題類似：即用1 x 2的多米諾骨牌填滿M x N的矩形有多少種方案，M<=5，N<2^31，輸出答案mod p的結果