5.10 本章习题

## 本章动态规划的习题 ##### [](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的结果