本帖子已过去太久远了，不再提供回复功能。C++数据结构原理与经典问题求解 pdf格式
为鼓励上传资源，我们采用积分下载方式，希望您能发布更多更好的资源互相分享
1.上传软件或电子书,源码,资料等,审核后即获2积分;如发布时设了下载需积分，其他用户下载后你将获得相应积分
2.当您首次注册时，可以获送10个下载积分，供您下载资源和熟悉网站下载的使用
3.发现资源有误或其他问题，通过举报按钮反馈后我们将奖励积分
4.您可以在论坛通过发帖等方式获取
5.参加本站可以在有效期内不限次数下载
6.您也（1元=10积分）或
7.我们会不定期举办各种活动，参加活动可以获取积分，请关注下载频道首页公告。
您可能遇到这些“伪问题”：
1.资料无法解压：
请确保所有分卷均下载完毕，如果有未知后缀文件，请搜索相应解压软件；
2.chm文件无内容：
您的电脑锁定了这一文件，请右击文件属性，点击右下方“解除锁定”，关闭文件后再打开；
3.下载不下来：
请尝试重新下载（重新下载不扣积分）；
4.杀毒软件报毒：
黑客安全及破解类软件容易报毒，但可正常使用，如担心安全请谨慎使用。
C++数据结构原理与经典问题求解
第1章 绪论 1
1.1 数据与数据结构 2
1.1.1 数据及其类型 2
1.1.2 数据结构简介 4
1.2 算法 6
1.2.1 算法的概念 6
1.2.2 算法的分析 8
1.2.3 算法的设计 12
1.3 C++语言简介 18
1.3.1 C++的产生与发展 18
1.3.2 C++与面向对象思想 20
1.3.3 C++中的类和对象 23
1.4 本章小结 28
第2章 C++基础 29
2.1 开始C++编程 30
2.1.1 输入输出 30
2.1.2 预处理 38
2.1.3 名字空间 44
2.2 深入的类编程 50
2.2.1 访问控制 50
2.2.2 初始化与清除 53
2.2.3 动态创建对象 57
2.2.4 友元函数 60
2.2.5 拷贝构造函数 61
2.3 丰富的C++特性 65
2.3.1 常量 65
2.3.2 函数重载 68
2.3.3 运算符重载 71
2.3.4 异常处理 77
2.4 代码重用机制 79
2.4.1 继承 80
2.4.2 多态 87
2.4.3 模板 90
2.5 标准模板库 93
2.5.1 STL简介 94
2.5.2 STL构成 95
2.5.3 STL的不同版本 97
2.6 本章小结 98
第3章 指针、数组与字符串 99
3.1 指针 100
3.1.1 指针的概念 100
3.1.2 指针的语法 102
3.1.3 函数与参数传递 103
3.2 数组 108
3.2.1 数组定义与初始化 109
3.2.2 数组与指针 113
3.2.3 数组的抽象数据类型 116
3.2.4 大整数乘法问题 120
3.2.5 荷兰国旗问题 121
3.3 字符串 124
3.3.1 C++中的字符串 124
3.3.2 字符串抽象数据类型 126
3.3.3 字符串的匹配算法 128
3.3.4 字符串指数问题 141
3.4 动态内存管理 142
3.4.1 关键词new和delete 143
3.4.2 避免内存错误 146
3.5 本章小结 152
第4章 链表 153
4.1 单向链表 154
4.1.1 单向链表的结构 154
4.1.2 单向链表类的实现 155
4.1.3 有序链表的合并 162
4.1.4 多项式加法问题 163
4.2 单向循环链表 164
4.2.1 单向循环链表的结构 164
4.2.2 单向循环链表类的实现 166
4.2.3 约瑟夫问题 169
4.2.4 魔术师发牌问题 170
4.2.5 拉丁方阵问题 172
4.3 双向循环链表 173
4.3.1 双向循环链表的结构 173
4.3.2 双向循环链表类的实现 174
4.3.3 Vigenere问题 182
4.3.4 选美比赛问题 184
4.4 游标类的设计与实现 186
4.4.1 游标类的结构 186
4.4.2 游标类的实现 187
4.5 STL与链表 191
4.5.1 STL中链表类的接口 191
4.5.2 遍历 194
4.5.3 元素的插入与删除 196
4.6 本章小结 196
第5章 栈与队列 197
5.1 栈 198
5.1.1 栈的结构 198
5.1.2 栈的实现 199
5.1.3 括号匹配问题 203
5.1.4 停车场模拟问题 204
5.2 队列 208
5.2.1 队列的结构 208
5.2.2 队列的实现 210
5.2.3 舞伴问题 214
5.2.4 杨辉三角形问题 215
5.2.5 游程编码问题 216
5.3 优先级队列 218
5.3.1 优先级队列的结构 218
5.3.2 优先级队列的实现 220
5.4 STL中的栈与队列 222
5.4.1 STL中的stack 222
5.4.2 STL中的queue 224
5.4.3 STL中的priority_queue 226
5.5 本章小结 229
第6章 递归 231
6.1 递归的概念 232
6.1.1 递归的定义 232
6.1.2 应用递归的原则 235
6.1.3 递归和非递归的转化 240
6.2 分治法 243
6.2.1 分治法简述 243
6.2.2 汉诺塔问题 244
6.2.3 传染病问题 246
6.3 回溯法 250
6.3.1 回溯法简述 251
6.3.2 迷宫问题 251
6.3.3 八皇后问题 255
6.3.4 骑士周游问题 258
6.4 本章小结 265
第7章 树 267
7.1 树的概念 268
7.1.1 树的定义 268
7.1.2 树的术语 271
7.1.3 树的抽象数据类型 272
7.2 二叉树 273
7.2.1 二叉树的定义 273
7.2.2 二叉树的性质 275
7.2.3 二叉树的实现 276
7.2.4 二叉树的遍历 285
7.2.5 二叉树的线索化 289
7.3 树与森林 291
7.3.1 树的存储表示 291
7.3.2 树的实现 294
7.3.3 树与森林的遍历 298
7.3.4 森林与二叉树的转换 300
7.4 霍夫曼树 304
7.4.1 霍夫曼树的概念 304
7.4.2 霍夫曼树的构造方法 305
7.4.3 霍夫曼编码及其实现 307
7.5 堆 313
7.5.1 堆的概念 314
7.5.2 堆的建立 314
7.5.3 堆的操作 316
7.6 基于STL实现树结构 317
7.6.1 STL中的vector 317
7.6.2 STL中的map 321
7.7 医院建模问题 323
7.8 本章小结 328
第8章 图 329
8.1 图的基本概念 330
8.1.1 图的定义 330
8.1.2 图的术语 331
8.1.3 图的运算 334
8.1.4 图的抽象数据类型 336
8.2 图的存储与表示 337
8.2.1 图的邻接矩阵表示 337
8.2.2 图的邻接表表示 339
8.2.3 两种表示法的比较 342
8.3 图的遍历 342
8.3.1 欧拉路径与欧拉回路 343
8.3.2 哈密尔顿路径与哈密尔顿回路 345
8.3.3 广度优先遍历 346
8.3.4 深度优先遍历 349
8.4 最短路径问题 353
8.4.1 固定起点最短路问题 353
8.4.2 非固定起点最短路问题 355
8.4.3 最短路径的动态规划解法 358
8.4.4 旅游交通路线问题 364
8.5 最小生成树 372
8.5.1 最小生成树的定义 372
8.5.2 克鲁斯卡尔算法 373
8.5.3 普里姆算法 375
8.6 经典问题举例 379
8.6.1 文字游戏问题 380
8.6.2 道路修建问题 382
8.6.3 回家路线问题 385
8.6.4 水塘计算问题 387
8.6.5 棍子还原问题 389
8.7 本章小结 392
第9章 树形搜索结构 393
9.1 二叉搜索树 394
9.1.1 二叉搜索树的概念 394
9.1.2 二叉搜索树的操作 395
9.1.3 二叉搜索树的实现 397
9.1.4 二叉搜索树的分析 400
9.2 AVL树 403
9.2.1 AVL树的概念 404
9.2.2 AVL树的旋转 405
9.2.3 AVL树的实现 410
9.3 红黑树 418
9.3.1 红黑树的概念 418
9.3.2 红黑树的操作 421
9.3.3 红黑树的实现 428
9.4 Trie树 433
9.4.1 Trie树的概念 433
9.4.2 Trie树的表示 434
9.4.3 Trie树的实现 435
9.5 本章小结 439
第10章 集合与字典 441
10.1 集合论基础 442
10.1.1 集合的概念 442
10.1.2 集合的运算 444
10.2 集合的实现 445
10.2.1 位向量集合 445
10.2.2 链表集合 451
10.3 字典 460
10.3.1 字典的概念 461
10.3.2 搜索运算 463
10.4 散列 467
10.4.1 散列的概念 467
10.4.2 散列函数 469
10.4.3 处理散列冲突 471
10.4.4 散列的应用 475
10.5 经典问题举例 476
10.5.1 拼写检查问题 476
10.5.2 无线网络问题 485
10.5.3 第K个数问题 488
10.6 STL中的set 490
10.7 本章小结 493
第11章 排序 495
11.1 排序问题概述 496
11.1.1 基本概念和定义 496
11.1.2 排序算法的分类 497
11.1.3 排序算法分析与选择 497
11.2 插入排序 498
11.2.1 直接插入排序 498
11.2.2 二分法插入排序 501
11.2.3 希尔排序 503
11.3 选择排序 506
11.3.1 直接选择排序 506
11.3.2 堆排序 508
11.4 交换排序 512
11.4.1 冒泡法排序 512
11.4.2 Shaker排序 514
11.4.3 快速排序 517
11.5 归并排序 522
11.6 计数排序 526
11.7 本章小结 531
参考文献 & 533
您对本软件有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力
下载地址：
您正在下载：C++数据结构原理与经典问题求解 pdf格式
热门最新推荐
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。
(window.slotbydup=window.slotbydup || []).push({
id: '2467142',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'小木虫 --- 500万硕博科研人员喜爱的学术科研平台
&&查看话题
求解数据结构链表问题答案
已知一个循环单链表la，av是可利用栈的头指针，请用３个赋值语句，完成将整个循环链表释放的功能。（即将表整个归还到可用的栈空间）
有误，没考虑到循环……
研究生必备与500万研究生在线互动！
扫描下载送金币
浏览器进程
打开微信扫一扫
随时随地聊科研同济大学图书馆v5.5书目检索系统
把本书分享到
收藏此书的书架
MARC状态：审校
文献类型：中文图书 浏览次数：68
题名/责任者:
.C++版/Mark Allen Weiss著 张丽萍译
出版发行项:
北:清华大学Q版社,2005
ISBN及定价:
7-302-11166-9/CNY86.00
载体形态项:
XIX, 738页:V26cm
并列正题名:
.计算机科学与技术
个人责任者:
M. A.
个人次要责任者:
-教材
-程序计-教材
非控制主题词:
中图法分类号:
中图法分类号:
中图法分类号:
据原书第2版译Q。
相关题名附注:
英文并列题名取封面
责任者附注:
责者规范中译姓 : 韦e
有书v。
提要文摘附注:
本书内容分为五部分。第一部分是对象和C++，包b对象和类、计模式等；第二部分是算法和构代码块，包b算法分析、随机等；第三部分是应用程序，包b真、V和径等；第V部分是实现，包b树、散列表等；第五部分是高级数据结构，包b伸展树等。
全部MARC细节信息>>
总体评价: (共0人) &&&我的评价:
TP312C++/ZW313-2
嘉定校区图书馆(中文)
TP312C++/ZW313-2
嘉定校区图书馆(中文)
TP312C++/ZW313-2
沪西图书阅览室
TP312C++/ZW313-2
沪西图书阅览室
TP312C++/ZW313-2
总馆借书处
TP312C++/ZW313-2
总馆科技图书阅览室（中文）
阅览楼二楼
TP312C++/ZW313-2
总馆科技图书阅览室（中文）
阅览楼二楼
显示全部馆藏信息
您可能感兴趣的图书(点击查看)
同名作者的其他著作(点击查看)
请输入下面显示的内容常见的动态规划问题分析与求解
动态规划（Dynamic Programming，简称DP），虽然抽象后进行求解的思路并不复杂，但具体的形式千差万别，找出问题的子结构以及通过子结构重新构造最优解的过程很难统一，并不像回溯法具有解决绝大多数问题的银弹（)。为了解决动态规划问题，只能靠多练习、多思考了。本文主要是对一些常见的动态规划题目的收集，希望能有所帮助。难度评级受个人主观影响较大，仅供参考。
目录（点击跳转）
动态规划求解的一般思路：&
判断问题的子结构（也可看作状态），当具有最优子结构时，动态规划可能适用。
求解重叠子问题。一个递归算法不断地调用同一问题，递归可以转化为查表从而利用子问题的解。分治法则不同，每次递归都产生新的问题。
重新构造一个最优解。
备忘录法：
动态规划的一种变形，使用自顶向下的策略，更像递归算法。
初始化时表中填入一个特殊值表示待填入，当递归算法第一次遇到一个子问题时，计算并填表；以后每次遇到时只需返回以前填入的值。
实例可以参照矩阵链乘法部分。&
1.硬币找零
难度评级：★
假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。&
用待找零的数值k描述子结构/状态，记作sum[k]，其值为所需的最小硬币数。对于不同的硬币面值coin[0...n]，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], ...)+1。对应于给定数目的找零total，需要求解sum[total]的值。
typedef struct {
int nC //使用硬币数量
//以下两个成员是为了便于构造出求解过程的展示
int lastS//上一个状态
int addC//从上一个状态达到当前状态所用的硬币种类
state *sum = malloc(sizeof(state)*(total+<span style="color:#));
for(i=<span style="color:#;i&=i++)
sum[i].nCoin = INF;
sum[<span style="color:#].nCoin = <span style="color:#;
sum[<span style="color:#].lastSum = <span style="color:#;
for(i=<span style="color:#;i&=i++)
for(j=<span style="color:#;j&n;j++)
if(i-coin[j]&=<span style="color:# && sum[i-coin[j]].nCoin+<span style="color:#&sum[i].nCoin)
sum[i].nCoin = sum[i-coin[j]].nCoin+<span style="color:#;
sum[i].lastSum =
sum[i].addCoin = coin[j];
if(sum[total].nCoin == INF)
printf(&can't make change.\n&);
return <span style="color:#;
通过sum[total].lastSum和sum[total].addCoin，很容易通过循环逆序地或者编写递归调用的函数正序地输出从结束状态到开始状态使用的硬币种类。以下各题输出状态转换的方法同样，不再赘述。下面为了方便起见，有的题没有在构造子结构的解时记录状态转换，如果需要请类似地完成。
(1)一个矩形区域被划分为N*M个小矩形格子，在格子(i,j)中有A[i][j]个苹果。现在从左上角的格子(1,1)出发，要求每次只能向右走一步或向下走一步，最后到达(N,M)，每经过一个格子就把其中的苹果全部拿走。请找出能拿到最多苹果数的路线。
难度评级：★
这道题中，当前位置(i,j)是状态，用M[i][j]来表示到达状态(i,j)所能得到的最多苹果数，那么M[i][j] = max(M[i-1][j],M[i][j-1]) + A[i][j] 。特殊情况是M[1][1]=A[1][1]，当i=1且j!=1时,M[i][j] = M[i][j-1] + A[i][j]；当i!=1且j=1时M[i][j] = M[i-1][j] + A[i][j]。
求解程序略。
(2)装配线调度（《算法导论》15.1）
难度评级：★
2.字符串相似度/编辑距离（edit distance）
难度评级：★
对于序列S和T，它们之间距离定义为：对二者其一进行几次以下的操作(1)删去一个字符；(2)插入一个字符；(3)改变一个字符。每进行一次操作，计数增加1。将S和T变为同一个字符串的最小计数即为它们的距离。给出相应算法。
将S和T的长度分别记为len(S)和len(T)，并把S和T的距离记为m[len(S)][len(T)]，有以下几种情况：
如果末尾字符相同，那么m[len(S)][len(T)]=m[len(S)-1][len(T)-1]；
如果末尾字符不同，有以下处理方式
修改S或T末尾字符使其与另一个一致来完成，m[len(S)][len(T)]=m[len(S)-1][len(T)-1]+1；
在S末尾插入T末尾的字符，比较S[1...len(S)]和S[1...len(T)-1]；
在T末尾插入S末尾的字符，比较S[1...len(S)-1]和S[1...len(T)]；
删除S末尾的字符，比较S[1...len(S)-1]和S[1...len(T)]；
删除T末尾的字符，比较S[1...len(S)]和S[1...len(T)-1]；
总结为，对于i&0,j&0的状态(i,j),m[i][j] = min( m[i-1][j-1]+(s[i]==s[j])?0:1 , m[i-1][j]+1, m[i][j-1] +1)。
这里的重叠子结构是S[1...i]，T[1...j]。
以下是相应代码。考虑到C语言数组下标从0开始，做了一个转化将字符串后移一位。
#include &stdio.h&
#include &string.h&
#define MAXLEN 20
#define MATCH 0
#define INSERT 1
#define DELETE 2
typedef struct {
cell m[MAXLEN+<span style="color:#][MAXLEN+<span style="color:#];
int match(char a,char b)
//cost of match
//not match:1
return (a==b)?<span style="color:#:<span style="color:#;
int string_compare(char *s,char *t)
int i,j,k;
int opt[<span style="color:#];
//row_init(i);
for(i=<span style="color:#;i&=MAXLEN;i++) {
m[i][<span style="color:#].cost =
if(i==<span style="color:#)
m[i][<span style="color:#].parent = -<span style="color:#;
m[i][<span style="color:#].parent = INSERT;
//column_init(i);
for(i=<span style="color:#;i&=MAXLEN;i++) {
m[<span style="color:#][i].cost =
if(i==<span style="color:#)
m[<span style="color:#][i].parent = INSERT;
char m_s[MAXLEN+<span style="color:#] = & &,m_t[MAXLEN+<span style="color:#] =& &;
strcat(m_s,s);
strcat(m_t,t);
for(i=<span style="color:#;i&=strlen(s);i++)
for(j=<span style="color:#;j&=strlen(t);j++) {
opt[MATCH] = m[i-<span style="color:#][j-<span style="color:#].cost + match(m_s[i],m_t[j]);
opt[INSERT] = m[i][j-<span style="color:#].cost + <span style="color:#;
opt[DELETE] = m[i-<span style="color:#][j].cost + <span style="color:#;
m[i][j].cost = opt[MATCH];
m[i][j].parent = MATCH;
for(k=INSERT;k&=DELETE;k++)
if(opt[k]&m[i][j].cost)
m[i][j].cost = opt[k];
m[i][j].parent =
//goal_cell(s,t,&i,&j);
return m[i][j].
int main() {
char t[] = &you should not&;
char p[] = &thou shalt not&;
int n = string_compare(t,p);
printf(&%d\n&,n);
字符串相似度/edit distance
(1)子串匹配
难度评级：★★
修改两处即可进行子串匹配：
row_init(int i)
m[<span style="color:#][i].cost = <span style="color:#; /* note change */
m[<span style="color:#][i].parent = -<span style="color:#; /* note change */
goal_cell(char *s, char *t, int *i, int *j)
int /* counter */
*i = strlen(s) - <span style="color:#;
*j = <span style="color:#;
for (k=<span style="color:#; k&strlen(t); k++)
if (m[*i][k].cost & m[*i][*j].cost) *j =
如果j= strlen(S) - strlen(T)，那么说明T是S的一个子串。
（这部分是根据《算法设计手册》8.2.4和具体实例Skiena与Skienaa、Skiena与somta的分析获得的，解释不够全面，可能有误，请注意）
(2)最长公共子序列
难度评级：★★
将match时不匹配的代价转化为最大长度即可：
int match(char c, char d)
if (c == d) return(<span style="color:#);
else return(MAXLEN);
此时，最小值是两者不同部分的距离。
（这部分同样也不好理解，对于最长公共子序列，建议直接使用下一部分中的解法）
如果在编辑距离中各个操作的代价不同，如何寻找最小代价？&
3.最长公共子序列(Longest Common Subsequence,lcs)
难度评级：★
对于序列S和T，求它们的最长公共子序列。例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}则它们的lcs是{B,C,B,A}和{B,D,A,B}。求出一个即可。
和2类似，对于X[1...m]和Y[1...n]，它们的任意一个lcs是Z[1...k]。
(1)如果X[m]=Y[n]，那么Z[k]=X[m]=Y[n],且Z[1...k-1]是X[1...m-1]和Y[1...n-1]的一个lcs；
(2)如果X[m]!=Y[n]，那么Z[k]!=X[m]时Z是X[1...m-1]和Y的一个lcs；
(3)如果X[m]!=Y[n]，那么Z[k]!=Y[n]时Z是X和Y[1...n-1]的一个lcs；
下面是《算法导论》上用伪码描述的lcs算法。其中c[i][j]记录当前lcs长度，b[i][j]记录到达该状态的上一个状态。
如何输出所有的LCS？
难度评级：★★
根据上面c[i,j]和b[i,j]的构造过程可以发现如果c[i-1,j]==c[i,j-1]，那么分别向上和向左返回的上一个状态都是可行的。如果将其标记为“左/上”并通过递归调用来生成从c[m,n]到c[1,1]的所有路径，就能找出所有的LCS。时间复杂度上界为O(mn)。
通过LCS获得最长递增自子序列。
对于1个序列，如，最大值9，最小值1，那么通过将它与求LCS得到的就是最长连续递增子序列23568。
这种做法不适用于最长连续非递减子序列，除非能获得重复最多的元素数目，如，那么可以用778899与之比较。
使用专门的最长递增子序列算法可以进行优化，详见下一部分。
4.最长递增子序列（Longest Increasing Subsequence,lis）
难度评级：★
& 对于一个序列如1，-1，2，-3，4，-5，6，-7，其最长第增子序列为1,2,4,6。
除了利用3中lcs来求解，这里使用求解lis问题的专门方法。
先看看如何确定子结构的表示。对于长度为k的序列s[1...k]，如果用lis[k]记录这个序列中最长子序列似乎没什么用，因为在构造lis[k+1]时，需要比较s[k]与前面长度为lis[k]的lis的最后一个元素、s[1...k]中长度为lis[k]-1的序列的最后一个元素等等，没有提供什么便利，这个方案被否决。
为了将每个lis[k]转化为构造lis[k+1]时有用的数据，把子结构记为以s[k]为结尾的lis的长度，那么对于s[k+1]，需要检查所有在它前面且小于它的元素s[i]，并令lis[k+1] = max(lis[i]+1),（i=1 to k,s[k+1]&s[i]）。这样，一个O(n2)的算法便写成了。为了在处理完成后不必再一次遍历lis[1...n]，可以使用一个MaxLength变量保存当前记录中最长的lis。
typedef struct {
//算法核心
state *a = malloc(sizeof(state) * n);
for(i=<span style="color:#;i&n;i++) {
a[i].length = <span style="color:#;
a[i].prev = -<span style="color:#;
for(i=<span style="color:#;i&n;i++)
for(j=<span style="color:#;j&i;j++)
if(array[i]&array[j] && a[i].length & a[j].length + <span style="color:#)
a[i].length = a[j].length + <span style="color:#;
a[i].prev =
if(a[i].length & max_length) {
max_length = a[i].
求解lis的加速
&难度评级：★★
在构造lis[k+1]的时候可以发现，对于s[k+1]，真正有用的元素s[i]&s[k+1]且lis[i]最大。如果记录了不同长度的lis的末尾元素，那么对于新加入的元素s[k+1]，找出前面比它小的且对应lis最长的，就是以s[k+1]为结尾的lis[k+1]的长度。
可以发现使用数组MaxV[1...MAXLENGTH]其中MaxV[i]表示长度为i的lis的最小末尾元素，完全可以在s[k+1]时进行lis[k+1]的更新。进一步地发现，其实lis[]数组已经没有用了，对于MaxV[1...MAXLENGTH]中值合法对应的最大下标，就是当前最长的lis，也即利用MaxV[]更新自身。
同时，根据MaxV[]的更新过程，可以得出当i&j时，MaxV[i]&MaxV[j]（假设出现了i&j且Max[i]=&Max[j]的情况，那么在之前的处理中，在发现j长度的lis时，应用它的第i个元素来更新Max[i]，仍会导致MaxV[i]&MaxV[j]，这与这个现状发生了矛盾，也即这个情况是不可能到达的）。这样，在寻找小于s[k+1]的值时，可以使用二分查找，从而把时间复杂度降低至O(nlogn)。
int lis_ologn(int *array, int length) {
int i, left,right,mid,max_len = <span style="color:#;
int *MaxV;
if(!array)
return <span style="color:#;
MaxV = (int*)malloc(sizeof(int)*(length+<span style="color:#));
MaxV[<span style="color:#] = -<span style="color:#;
MaxV[<span style="color:#] = array[<span style="color:#];
for(i=<span style="color:#;i&i++){
//寻找范围是MaxV[1, ... , max_len]
left = <span style="color:#;
right = max_
//二分查找MaxV中第一个大于array[i]的元素
while(left&right) {
mid = (left+right)/<span style="color:#;
if(MaxV[mid]&=array[i])
left = mid + <span style="color:#;
else if(MaxV[mid]&array[i])
if((MaxV[right]&array[i])&&(MaxV[right-<span style="color:#]&array[i]))
MaxV[right] = array[i];
else if (MaxV[right]&array[i]) {
MaxV[right+<span style="color:#] = array[i];
max_len++;
return max_
& 在这个解法下，不妨考虑如何重构这个lis。
5.最大连续子序列和/积
难度评级：★
输入是具有n个数的向量x，输出时输入向量的任何连续子向量的最大和。
求和比较简单，以前写过比较全面的分析：
这里只把O(n)的动态规划解法列在下面，其中只用一个变量保存过去的状态：
int max_array_v4(int *array,int length) {
int maxsofar = NI;
int maxendinghere = <span style="color:#;
for(i=<span style="color:#;i&i++) {
maxendinghere = maxnum(maxendinghere + array[i],array[i]);
//分析：maxendinghere必须包含array[i]
//当maxendinghere&0且array[i]&0，maxendinghere更新为两者和
//当maxendinghere&0且array[i]&0，maxendinghere更新为两者和
//当maxendinghere&0且array[i]&0，maxendinghere更新为array[i]
//当maxendinghere&0且array[i]&0，maxendinghere更新为array[i]
maxsofar = maxnum(maxsofar,maxendinghere);
难度评级：★
给定一个正浮点数数组，求它的一个最大连续子序列乘积的值。
对数组中每个元素取对数，构成新的数列，在新的数列上使用求最大连续子序列的算法。
如果求对数开销较大，建议使用扩展2的方法。
难度评级：★
给定一个浮点数数组，其值可正可负可零，求它的一个最大连续子序列乘积的值。（假定计算过程中，任意一个序列的积都不超过浮点数最大表示）
在最大连续子序列和算法的基础上进行修改。由于负负得正，对于当前状态array[k]，需要同时计算出它的最大值和最小值。即：
new_maxendinghere = max3(maxendinghere*array[k],minendinghere*array[k],array[k])
new_minendinghere = min3(maxendinghere*array[k],minendinghere*array[k],array[k])
此后对已遍历部分的最大积进行更新：
maxsofar = max(maxsofar,new_maxendinghere)
如果不习惯用常数个变量来表示，可以看看，再想想用数组保存是不是浪费了空间。（计算max[k]、min[k]只用到了max[k-1]、min[k-1]，没有必要保存全部状态）
6.矩阵链乘法
难度评级：★
一个给定的矩阵序列A1A2...An计算连乘乘积，有不同的结合方法，并且在结合时，矩阵的相对位置不能改变，只能相邻结合。根据矩阵乘法的公式，10*100和100*5的矩阵相乘需要做10*100*5次标量乘法。那么对于维数分别为10*100、100*5、5*50的矩阵A、B、C，用(A*B)*C来计算需要10*100*5 + 10*5*500 =7500次标量乘法；而A*(B*C)则需要100*5*50+10*100*50=75000次标量乘法。
那么对于由n个矩阵构成的链&A1,A2,...,An&，对i-1,2,...n，矩阵Ai的维数为pi-1*pi，对乘积A1A2...An求出最小化标量乘法的加括号方案。
尽管可以通过递归计算取1&=k&n使得P(n)=∑P(k)P(n-k)，遍历所有P(n)种方案，但这并不是一个高效率的解法。
经过以上几道题的锻炼，很容易看出，子结构是求Ai...Aj的加括号方法m[i][j]可递归地定义为
\[m[i][j]=\left\{\begin{matrix} 0& if \ i=j\\ \underset{i\leqslant k&j}{min}\begin{Bmatrix} m[i][k] + & m[k+1][j] +& p_{i-1}p_{k}p_{j} \end{Bmatrix} & if \ i&j \end{matrix}\right.\]
这样，只需利用子结构求解m[1][n]即可，并在在构造m[1][n]的同时，记录状态转换。下面的代码展示了这个过程，不再仔细分析。
#include &stdio.h&
#include &stdlib.h&
#define ULT
int print_optimal_parens(int **s,int i, int j)
printf(&A%d&,i+<span style="color:#);
printf(&(&);
print_optimal_parens(s,i,*(*(s+i)+j));
print_optimal_parens(s,*(*(s+i)+j)+<span style="color:#,j);
printf(&)&);
return <span style="color:#;
int matrix_chain_order(int *p, int n) {
int i,j,k,l,q;
int **m, **s;
m=(int **)malloc(n*sizeof(int*));
for(i=<span style="color:#;i&n;i++)
m[i]=(int*)malloc(n*sizeof(int));
s=(int **)malloc(n*sizeof(int*));
for(i=<span style="color:#;i&n;i++)
s[i]=(int*)malloc(n*sizeof(int));
for(i=<span style="color:#;i&n;i++)
s[i][i] = <span style="color:#;
//m,s可以被压缩存储在上三角矩阵
for(l=<span style="color:#;l&=n;l++) {
for (i=<span style="color:#;i&n-l+<span style="color:#;i++) {
j = i+l-<span style="color:#;
m[i][j] = ULT;
for (k=i; k&j;k++)
q = m[i][k] + m[k+<span style="color:#][j] + p[i-<span style="color:#+<span style="color:#]*p[k+<span style="color:#]*p[j+<span style="color:#];
if (q&m[i][j])
/*display m[i][j]*/
for (i=0;i&n;i++) {
for (j=0;j&n;j++)
printf(&%d &,m[i][j]);
printf(&\n&);
print_optimal_parens(s,<span style="color:#,<span style="color:#);
printf(&\n&);
return <span style="color:#;
int main() {
int p[] = {<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#};
n = (sizeof(p)/sizeof(int))-<span style="color:#;
matrix_chain_order(p,n);
return <span style="color:#;
矩阵链乘法
矩阵链乘法的备忘录解法（伪码），来自《算法导论》第15章。
难度评级：★★
一个贼在偷窃一家商店时发现了n件物品，其中第i件值vi元，重wi磅。他希望偷走的东西总和越值钱越好，但是他的背包只能放下W磅。请求解如何放能偷走最大价值的物品，这里vi、wi、W都是整数。
如果每个物品都允许切割并只带走其一部分，则演变为部分背包问题，可以用贪心法求解。0-1背包问题经常作为贪心法不可解决的实例（可通过举反例来理解），但可以通过动态规划求解。
为了找出子结构的形式，粗略地分析发现，对前k件物品形成最优解时，需要决策第k+1件是否要装入背包。但是此时剩余容量未知，不能做出决策。因此把剩余容量也考虑进来，形成的状态由已决策的物品数目和剩余容量两者构成。这样，所有状态可以放入一个n*(W+1)的矩阵c中，其值为当前包中物品总价值，这时有
\[c[i][j]=\left\{\begin{matrix} c[i-1][j]& if \ w_{i}&j\\ \max\begin{Bmatrix} c[i-1][j-w_{i}]+v_{i} \ ,\ c[i-1][j] \end{Bmatrix} & if \ w_{i}\leqslant j \end{matrix}\right.\]
根据这个递推公式，很容易写出求解代码。
#include &stdio.h&
#include &stdlib.h&
int package_dp(int *v,int *w,int n,int total) {
int i,j,tmp1,tmp2;
int **c = (int **)malloc((n+<span style="color:#)*sizeof(int *));
for(i=<span style="color:#;i&n+<span style="color:#;i++)
c[i]=(int *)malloc((total+<span style="color:#)*sizeof(int));
for(i=<span style="color:#,j=<span style="color:#;j&j++)
c[i][j] = <span style="color:#;
for(i=<span style="color:#;i&=n;i++) {
c[i][<span style="color:#] = <span style="color:#;
for(j=<span style="color:#;j&=j++) {
if(w[i]&j)
c[i][j] = c[i-<span style="color:#][j];
tmp1 = v[i]+c[i-<span style="color:#][j-w[i]];
tmp2 = c[i-<span style="color:#][j];
c[i][j]=(tmp1&tmp2?tmp1:tmp2);
printf(&c[%d][%d]:%d\n&,n,total,c[n][total]);
return <span style="color:#;
int main() {
int v[] = {<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#};
int w[] = {<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#};
int total = <span style="color:#0;
package_dp(v,w,sizeof(v)/sizeof(int)-<span style="color:#,total);
return <span style="color:#;
0-1背包问题示例代码
8.有代价的最短路径
难度评级：★★★
无向图G中有N个顶点，并通过一些边相连接，边的权值均为正数。初始时你身上有M元，当走过i点时，需要支付S(i)元，如果支付不起表示不能通过。请找出顶点1到顶点N的最短路径。如果不存在则返回一个特殊值，如果存在多条则返回最廉价的一条。限制条件：1&N&=100; 0&=M&=100 ; 对任意i, 0&=S[i]&=100。
如果不考虑经过顶点时的花费，这就简化成了一个一般的两点间最短路径问题，可以用Dijkstra算法求解。加入了花费限制之后，就不能直接求解了。
考察从顶点0到达顶点i的不同状态，会发现它们之间的区别是：总花费相同但路径长度不同、总花费不同但路径长度不同。为了寻找最短路径，必然要保存到达i点的最短路径；同时为了找到最小开销，应该把到达i点的开销也进行保存。根据题目的数值限制，可以将总开销作为到达顶点i的一个状态区分。这样，就可以把Min[i][j]表示为到达顶点i（并经过付钱）时还剩余j元钱的最短路径的长度。在此基础上修改Dijkstra算法，使其能够保存到达同一点不同花费时的最短长度，最终的Min[N-1][0...M]中最小的即为所求。以下是求解过程的伪代码。
对所有的(i,j),Min[i][j] = ∞,state[i][j] =
Min[<span style="color:#][M] = <span style="color:#;
while(<span style="color:#) {
for 所有unvisited的(i,j)找出M[i][j]最小的，记为(k,l)
if Min[k][l] = ∞
state[k][l] =
for 所有顶点k的邻接点p
if (l-S[p]&=<span style="color:# && Min[p][<span style="color:#-S[p]]&Min[k][l]+Dist[k][p])
Min[p][<span style="color:#-S[p]] = Min[k][l]+Dist[k][p];
//通过Dijstra算法寻找不同花费下的最小路径
for 所有j，找出Min[N-<span style="color:#][j]最小的
如果存在多个j，那么选出其中j最大的
9.瓷砖覆盖（状态压缩DP）
难度评级：★★★
用 1 * 2 的瓷砖覆盖 n * m 的地板，问共有多少种覆盖方式？
（启发来自于：，下文叙述做了点修改）
分析子结构，按行铺瓷砖。一块1*2瓷砖，横着放对下一行的状态没有影响；竖着放时，下一行的对应一格就会被占用。因此，考虑第i行的铺法时只需考虑由第i-1行造成的条件限制。枚举枚举第i-1行状态即可获得i行可能的状态，这里为了与链接一文一致，第i-1行的某格只有两个状态：空或者放置。空表示第i行对应位置需要放置一个竖着的瓷砖，这时在铺第i行时，除去限制以外，只需考虑放还是不放横着的瓷砖这2种情况即可（不必分为放还是不放、横到下一层还是竖着一共4种）。同时对于第i-1行的放法，用二进制中0和1表示有无瓷砖，那么按位取反恰好就是第i行的限制条件。
//原作者：limchiang
//出处：http://blog.csdn.net/limchiang/article/details/8619611
#include &stdio.h&
#include &string.h&
/** n * m 的地板 */
/** dp[i][j] = x 表示使第i 行状态为j 的方法总数为x */
__int64 dp[<span style="color:#][<span style="color:#49];
/* 该方法用于搜索某一行的横向放置瓷砖的状态数,并把这些状态累加上row-1 行的出发状态的方法数
* @name row 行数
* @name state 由上一行决定的这一行必须放置竖向瓷砖的地方，s的二进制表示中的1 就是这些地方
* @name pos 列数
* @name pre_num row-1 行的出发状态为~s 的方法数
void dfs( int row, int state, int pos, __int64 pre_num )
/** 到最后一列
if( pos == m ){
dp[row][state] += pre_
/** 该列不放 */
dfs( row, state, pos + <span style="color:#, pre_num );
/** 该列和下一列放置一块横向的瓷砖 */
if( ( pos &= m-<span style="color:# ) && !( state & ( <span style="color:# && pos ) ) && !( state & ( <span style="color:# && ( pos + <span style="color:# ) ) ) )
dfs( row, state | ( <span style="color:# && pos ) | ( <span style="color:# && ( pos + <span style="color:# ) ), pos + <span style="color:#, pre_num );
int main()
while( scanf(&%d%d&,&n,&m) && ( n || m ) ){
/** 对较小的数进行状压，已提高效率 */
if( n & m ){
memset( dp, <span style="color:#, sizeof( dp ) );
/** 初始化第一行 */
dfs( <span style="color:#, <span style="color:#, <span style="color:#, <span style="color:# );
for( int i = <span style="color:#; i &= i ++ )
for( int j = <span style="color:#; j & ( <span style="color:# && m ); j ++ ){
if( dp[i-<span style="color:#][j] ){
__int64 tmp = dp[i-<span style="color:#][j];
/* 如果i-1行的出发状态某处未放，必然要在i行放一个竖的方块，
* 所以我对上一行状态按位取反之后的状态就是放置了竖方块的状态
dfs( i, ( ~j ) & ( ( <span style="color:# && m ) - <span style="color:# ), <span style="color:#, tmp ) ;
else continue;
/** 注意并不是循环i 输出 dp[n][i]中的最大值 */
printf( &%I64d\n&,dp[n][(<span style="color:#&&m)-<span style="color:#] );
return <span style="color:#;
10.工作量划分
难度评级：★★
假设书架上一共有9本书，每本书各有一定的页数，分配3个人来进行阅读。为了便于管理，分配时，各书要求保持连续，比如第1、2、3本书分配给第1人，4、5分配给第二人，6，7，8，9分配给第3人，但不能1，4，2分配给第1人，3，5，6分配给第2人。即用两个隔板插入8个空隙中将9本书分成3部分，书不能换位。同时，分配时必须整本分配，同一本书不能拆成两部分分给两个人。为了公平起见，需要将工作量最大的那一部分最小化，请设计分配方案。用s1,...,sn表示各本书的页数。
继续从子结构的角度出发，发现如果前面的k-1份已经分好了，那么第k份自然也就分好了。用M[n][k]表示将n本书分成k份时最小化的k份中的最大工作量，从第k份也就是最后一份的角度来看，总数-它的不同情况下数量 = 前k-1份的数量和。
\[M[n][k] = \overset{n}{\underset{i=1}{min}}\max(M[i][k-1],\sum_{j=i+1}^{n}s_{j})\]
& 除此以外，初始化为
\[M[1][k] = s_{1},for \ all \ k&0\\ M[n][1] = \sum_{i=1}^{n}s_{1}\]
自底向上地可以求得使M[n][k]最小化的解。
#include &stdio.h&
#define MAXN 9
#define MAXINT 32767
void print_books(int s[],int start,int end);
int reconstruct_partition(int s[],int d[MAXN+<span style="color:#][MAXN+<span style="color:#],int n,int k);
int max(int a,int b);
int max(int a,int b)
int partition(int s[],int n,int k)
int m[MAXN+<span style="color:#][MAXN+<span style="color:#];
int d[MAXN+<span style="color:#][MAXN+<span style="color:#];
int p[MAXN+<span style="color:#];
int i,j,x;
p[<span style="color:#] = <span style="color:#;
for(i=<span style="color:#;i&=n;i++)
p[i] = p[i-<span style="color:#]+s[i-<span style="color:#];
for(i=<span style="color:#;i&=n;i++)
m[i][<span style="color:#] = p[i];
for(j=<span style="color:#;j&=k;j++)
m[<span style="color:#][j] = s[<span style="color:#];
for(i=<span style="color:#;i&=n;i++)
for(j=<span style="color:#;j&=k;j++)
m[i][j] = MAXINT;
for(x=<span style="color:#;x&=(i-<span style="color:#);x++)
cost = max(m[x][j-<span style="color:#],p[i]-p[x]);
if(m[i][j]&cost) {
reconstruct_partition(s,d,n,k);
int reconstruct_partition(int s[],int d[MAXN+<span style="color:#][MAXN+<span style="color:#],int n,int k)
if(k==<span style="color:#)
print_books(s,<span style="color:#,n);
reconstruct_partition(s,d,d[n][k],k-<span style="color:#);
print_books(s,d[n][k]+<span style="color:#,n);
return <span style="color:#;
void print_books(int s[],int start,int end)
for(i=i&=i++)
printf(& %d &,s[i-<span style="color:#]);
printf(&\n&);
int main() {
int a[] = {<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#};
int b[] = {<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#,<span style="color:#};
printf(&first:\n&);
partition(a,<span style="color:#,<span style="color:#);
printf(&\nsecond:\n&);
partition(b,<span style="color:#,<span style="color:#);
return <span style="color:#;
工作量划分
这个问题被称为线性分割(linear partition)问题，有不少的应用情形。如，一系列任务分配给几个并行进程，那么分配工作量最大任务的那个进程将成为影响最终完成时间的瓶颈。将最大的工作量尽量减少，能够使所有工作更快地完成。
11.三次捡苹果
难度评级：★★★
（问题1的相关问题(1)的进一步扩展）一个矩形区域被划分为N*M个小矩形格子，在格子(i,j)中有A[i][j]个苹果。现在从左上角的格子(1,1)出发，要求每次只能向右走一步或向下走一步，每经过一个格子就把其中的苹果全部拿走，最后到达(N,M)。此时，只允许向上或向左走一步，反方向走回(1,1)。这一趟可以不走第一趟的路线，但当经过第一趟所经过的格子时，里面已经没有苹果了。到达(1,1)后，再次反方向地只允许向右或向下走，走到(N,M)，同样可以不走前两趟走过的路线。求这三趟的走法，使得最终能拿取最多数量的苹果。
这个问题有两个难点，首先要理清三条路线的关系。可以发现，虽然第二趟方向相反，但其实和从(1,1)走到(N,M)是一样的，即三趟路线全部可以转化为从(1,1)向下或向右走到(N,M)的过程。
观察三条路线可以发现，实际中走的时候如果路线有交叉，可以把这种情况转化为相遇而不交错的情况如下图：
这样做的好处是，对于红线和蓝线上同一行j的点的坐标(i,j)(i',j)，总有i&=i',这样就能够把三条路线划分成左、中、右三条有序的路线。
经过两次转化，可以构造子结构了。用Max[y-1][i][j][k]表示在y-1行时，三条路线分别在i、j、k时所能取得的最大苹果数，用Max[y-1][i][j][k]可以求解任意的Max[y][i'][j'][k']，其中i' = i to j' , j' = j to k', k' = k to M. 如果线路重叠，苹果已经被取走，不用重复考虑。因此处理每一行时为了简单起见最好维护一个该位置苹果是否被取走的标志位，方便在路线重叠时计算。根据上面的范围关系，先求k'的所有情况，然后是j'，最后才是x'。这样Max[N][M][M][M]就是三趟后所能取得的最多苹果数。
《算法导论》第15章动态规划、第16章贪心算法
《算法设计手册》第八章动态规划
《编程珠玑》相关问题
《编程之美》相关问题
附录1：其他的一些动态规划问题与解答（链接）
& 评：网络上的很多中文版本，都不如直接看这篇文章里的英文原版解答理解的清楚。
评：难度不高，注意要求的是空格数的立方和最小。
评：需要一些马尔科夫链的知识。理解起来不是很容易，理解以后是不是有种像是更多个生产线的装备线调度？
评：和0-1背包问题何其相似。
附录2：《算法设计手册》第八章 动态规划 面试题解答
给定一个硬币种类的集合，找出凑出给定一个值所用的最小硬币数目。
正文问题1已做解答，略。
长度为n的数组，其中元素可正可负可零。找出数组索引i,j使得从i到j的元素之和最大。
最大连续自序列和问题，请参考正文问题5的解答。
假设你有一页纸，正面和背面都写满了字母，当剪掉正面上一个字母时，这一页的背面的字母也会被剪掉。设计一个算法来验证是否能通过这张纸生成一个给定的字符串？提供一个函数，当你输入一个字母的位置时能够返回它背面的字母。（叙述关键思路即可）
目前我所看到的最容易理解的解法是使用最大流来解的：
下面把思路大意翻译一下。
假设需要拼成的字符串是&FOO&，同时这张纸的正反面对应位置上的内容（可以通过提供的函数获得）分别是：
由于位置4上的字母的正反面都用不到，忽略。
把这个表格转化成一个两层结点的流量网络
其中源点下面第一层表示拼成所需字符串的所有字母，源点到达该点的流量是需要的数目。第一层与第二层相连接表示某一位置上对应的是哪个所需字母，比如位置1正反面分别是F和O，表示它能提供1个F的入度和1个O的入度，但又由于一个片纸无论正反面只能用一次，那么它只能提供1的出度，直接连接汇点。
这个问题是否有解，等价于这个流量网络中是否存在一个流使得源点的流的出度等于汇点流的的入度，即一个最大流问题。
看过本文的人也看了：
我要留言技术领域：
你已经自动关注本知识库了哦！
确定要取消收藏吗？
删除图谱提示
你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示
无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示
你确定要删除该知识节点吗？
