## 本章动态规划的习题
##### [](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),
[![](http://box.kancloud.cn/2015-07-06_5599fd308e899.png)](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)
[![](http://box.kancloud.cn/2015-07-06_5599fd443d6c2.png)](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种搭法,如下图所示:
[![](http://box.kancloud.cn/2015-07-06_5599fd5e8de26.png)](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的结果
- 关于
- 第一部分 数据结构
- 第一章 字符串
- 1.0 本章导读
- 1.1 旋转字符串
- 1.2 字符串包含
- 1.3 字符串转换成整数
- 1.4 回文判断
- 1.5 最长回文子串
- 1.6 字符串的全排列
- 1.10 本章习题
- 第二章 数组
- 2.0 本章导读
- 2.1 寻找最小的 k 个数
- 2.2 寻找和为定值的两个数
- 2.3 寻找和为定值的多个数
- 2.4 最大连续子数组和
- 2.5 跳台阶
- 2.6 奇偶排序
- 2.7 荷兰国旗
- 2.8 矩阵相乘
- 2.9 完美洗牌
- 2.15 本章习题
- 第三章 树
- 3.0 本章导读
- 3.1 红黑树
- 3.2 B树
- 3.3 最近公共祖先LCA
- 3.10 本章习题
- 第二部分 算法心得
- 第四章 查找匹配
- 4.1 有序数组的查找
- 4.2 行列递增矩阵的查找
- 4.3 出现次数超过一半的数字
- 第五章 动态规划
- 5.0 本章导读
- 5.1 最大连续乘积子串
- 5.2 字符串编辑距离
- 5.3 格子取数
- 5.4 交替字符串
- 5.10 本章习题
- 第三部分 综合演练
- 第六章 海量数据处理
- 6.0 本章导读
- 6.1 关联式容器
- 6.2 分而治之
- 6.3 simhash算法
- 6.4 外排序
- 6.5 MapReduce
- 6.6 多层划分
- 6.7 Bitmap
- 6.8 Bloom filter
- 6.9 Trie树
- 6.10 数据库
- 6.11 倒排索引
- 6.15 本章习题
- 第七章 机器学习
- 7.1 K 近邻算法
- 7.2 支持向量机
- 附录 更多题型
- 附录A 语言基础
- 附录B 概率统计
- 附录C 智力逻辑
- 附录D 系统设计
- 附录E 操作系统
- 附录F 网络协议