算法设计与分析期末知识点总结

一、概论

1、算法设计的目标：

（1）正确性

（2）可使用性（用户友好性）

（3）可读性

（4）健壮性

（5）高效率与低存储量需求

1. 算法特性：

• 有限性
• 确定性
• 可行性
• 输入性（零个或多个输入）
• 输出性（一个或多个输出）

1. 算法和数据结构的区别和联系：

数据结构时算法设计的基础。算法的操作对象是数据结构，在设计算法时通常要构建适合这种算法的数据结构。数据结构设计主要是选择数据的存储方式，例如确定求解问题中的数据采用数组存储还是链表存储等。算法设计就是在选定的存储结构上设计一个满足要求的好算法

另外，数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础

1. 算法设计的基本步骤：

1. 分析求解问题：确定求解问题的目标（功能）、给定的条件（输入）和生成的结果（输出）
2. 选择数据结构和算法设计策略：设计数据对象的存储结构，因为算法的效率取决于数据对象的存储表示。算法设计有一些通用策略，例如迭代法、分治法、动态规划和回溯法等，需要针对求解问题选择合适的算法设计策略
3. 描述算法：在构思和设计好一个算法后必须清楚、准确地将所设计的求解步骤记录下来，即描述算法
4. 证明算法正确性
5. 算法分析：同一问题的求解算法可能有多种，可以通过算法分析找到好的算法。一般来说，一个好的算法应该比同类算法的时间和空间效率高

1. 算法的执行时间主要与问题规模有关

1. 渐进符号：

二、递归

1、递归的定义：

在数学与计算机科学中，递归是指在函数的定义中又调用函数自身的方法。若p函数定义中调用p函数，称之为直接递归；若p函数定义中调用q函数，而q函数定义中又调用p函数，称之为间接调用（任何间接递归都可以等价地转化为直接递归）。

2、能够用递归解决的问题应该满足以下三个条件：

（1）需要解决的问题可以转化为一个或多个子问题来解决，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同

（2）递归调用的次数必须是有限的

（3）必须有结束递归的条件来终止递归

3、何时使用递归：

（1）定义是递归的：

eg.求n！和斐波那契（Fibonacci）数列

（2）数据结构是递归的：

eg.单链表、二叉树的二叉链存储结构

（3）问题的求解方法是递归的：

eg.汉诺塔问题

4、递归算法的执行过程：

（1）递归执行是通过系统栈实现的

（2）每递归调用一次就需将参数、局部变量和返回地址等作为一个栈元素进栈一次，最多的进栈元素个数称为递归深度，n越大，递归深度越深

（3）每当遇到递归出口或本次递归调用执行完毕时需要退栈一次，并恢复参数值等，当全部执行完毕时栈应该为空

5、这种自上而下将问题分解，再自下而上求值、合并，求出最后问题解的过程称为递归求解过程，它是一种分而治之的算法设计方法

6、提取递归模型的基本模型：

（1）对原问题f(sn)进行分析，抽象出合理的小问题f(sn-1)（与数学归纳法中假设n＝k-1时等式成立相似）

（2）假设f(sn-1)是可解的，在此基础上确定f(sn)的解，即给出f(sn)与f(sn-1)之间的关系（与数学归纳法中求证n=k时等式成立的过程相似）

（3）确定一个特定情况（如f(0)或f(1)）的解，由此作为递归出口（与数学归纳法求证n = 1或n = 0时等式成立相似）

7、用递归树求解递归方程：

1. 用主方法求解递归方程：

主方法中递归方程的一般形式：T(n) = aT(n/b) + f(n)

• 分治法

1. 分治法所能解决的问题具有的特征：

1. 该问题的规模缩小到一定的程度就可以容易地解决
2. 该问题可以分解为若干个规模较小的相似问题
3. 利用该问题分解出的子问题的解可以合并为该问题的解
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

1. 分治法的求解步骤

1. 分解成若干个子问题：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题
2. 求解子问题：若子问题规模较小，容易被解决，则直接求解，否则递归地求解各个子问题
3. 合并子问题：将各个子问题的解合并为原问题的解

1. 寻找两个等长有序序列的中位数：

使用二分法：

1. 分别求出a、b的中位数a[m1]和a[m2]
2. 若a[m1] = a[m2]，则a[m1]或a[m2]即为所求的中位数
3. 若a[m1] < a[m2]，则舍弃序列a中的前半部分（较小的一半），同时舍弃序列b中的后半部分（较大的一半），要求舍弃的长度相同
4. 若a[m1] >?a[m2]，则舍弃序列a中的后半部分（较大的一半），同时舍弃序列b中的前半部分（较小的一半），要求舍弃的长度相同

在保留的两个升序序列中重复上述过程直到两个序列中只含有一个元素为止，较小者即为所求的中位数

1. 求解最大连续子序列和问题

1. 对于含有n个整数的序列a[0...n - 1]，若n = 1，表示该序列仅含一个元素，如果该元素大于0，则返回该元素，否则返回0
2. 若n > 1，采用分治法求解最大连续子序列时取其中间位置mid = [(n - 1) / 2]，该子序列只可能出现在3个地方：
3. 若该子序列完全落在左半部，即a[0...mid]中，采用递归求出其最大连续子序列和maxLeftSum
4. 若该子序列完全落在右半部，即a[mid + 1...n - 1]中，采用递归求出其最大连续子序列和maxRightSum
5. 若该子序列跨越序列a的中部而占据左、右部分。也就是说，这种情况下最大和的连续子序列含有amid，则从左半部（含amid元素）求出maxLeftBorderSum，从右半部（不含amid元素）求出maxRightBorderSum，这种情况下的最大连续子序列和maxMidSum = maxLeftBorderSum + maxRightBorderSum

最后整个序列a的最大连续子序列和为maxLeftSum、maxRightSum和maxMidSum 中的最大值

1. 求解棋盘覆盖问题

1. 将棋盘划分为大小相同的4个象限
2. 考虑左上角象限，若特殊方格在此象限中，则将左上角象限再次划分为大小相同的4个象限，从而再进行判断
3. 若特殊方格不在此象限中，用t号L形骨牌覆盖右下角，同时将右下角作为特殊方格继续处理该象限
4. 考虑右上角象限，若特殊方格在此象限中，则将右上角象限再次划分为大小相同的4个象限，从而再进行判断
5. 若特殊方格不在此象限中，用t号L形骨牌覆盖左下角，同时将左下角作为特殊方格继续处理该象限
6. 考虑左下角象限，若特殊方格在此象限中，则将左下角象限再次划分为大小相同的4个象限，从而再进行判断
7. 若特殊方格不在此象限中，用t号L形骨牌覆盖右上角，同时将右上角作为特殊方格继续处理该象限
8. 考虑右下角象限，若特殊方格在此象限中，则将右下角象限再次划分为大小相同的4个象限，从而再进行判断
9. 若特殊方格不在此象限中，用t号L形骨牌覆盖左上角，同时将左上角作为特殊方格继续处理该象限

1. 求解循环日程安排问题

设有n = 2^k个选手要进行网球循环赛，设计一个满足一下要求的比赛日程表：

1. 每个选手必须与其他n - 1个选手各赛一次
2. 每个选手一天只能赛一次
3. 循环赛在n - 1天之内结束

解：采用分治策略可以将所有选手分为两半，2^k各选手的比赛日程表就可以通过2^(k - 1)个选手设计的比赛日程来决定，将n = 2^k问题划分为4个部分：

1. 左上角：左上角为2^(k - 1)个选手在前半程的比赛日程（k = 1时直接给出，否则上一轮求出的就是2^(k - 1)个选手的比赛日程）
2. 左下角：左下角为另2^(k - 1)个选手在前半程的比赛日程，由左上角加2^(k - 1)得到，例如2^2个选手比赛，左下角由左上角直接加2（2^(k - 1)）得到，2^3个选手比赛，左下角由左上角直接加4（2^(k - 1)）得到
3. 右上角：将左下角直接复制到右上角得到另2^(k - 1)个选手在后半程的比赛日程
4. 右下角：将左上角直接复制到右下角得到2^(k - 1)个选手在后半程的比赛日程

1. 求解大整数乘法问题

设X和Y都是n位的二进制整数，现在要计算它们的乘积X * Y

先将n位的二进制整数X和Y各分为两段，每段的长为n / 2位，因此，X = A * 2^(n / 2) + B，Y = C * 2^(n / 2) + D，这样，X和Y的乘积为：

X * Y = (A * 2^(n / 2) + B) * (C * 2^(n / 2) + D)

??????= A * C * 2^n + (A * D + B * C) * 2^(n / 2) + B * D

1. 并行算法是用多态处理器联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解

1. 为利用并行计算，通常计算问题的表现特征为：

1. 将工作分离成离散部分有助于同时解决。例如，对于分治法设计的串行算法，可以将各个独立的子问题并行求解，最后合并成整个问题的解，从而转化为并行算法
2. 随时并及时地执行多个程序指令
3. 多计算资源下解决问题地耗时要少于单个计算资源下的耗时

• 回溯法（DFS）

1、回溯法实际上是一个类似穷举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时就“回溯”（即回退），尝试其他路径

1. 一个复杂问题的解决方案是由若干个小的决策步骤组成的决策序列，所以一个问题的解可以表示成解向量X = (x1,x2,...,xn)，其中分量x1对应第i步的选择，通常可以有两个或者多个取值。X中各分量xi所有取值的组合构成问题的解向量空间，简称为解空间或者是解空间树，由于一个解向量往往对应问题的某个状态，所以解空间又称为问题的状态空间树

1. 用回溯法求解的问题：

1. 求一个（或全部）可行解
2. 求最优解

1. 解空间树通常有两种类型。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树；当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树

1. 回溯法：在包含问题的所有解的解空间树中给，按照深度优先搜索的策略，从根节点（开始结点）出发搜索解空间树，首先根节点成为活结点（活结点是指自身已生成但其孩子结点没有全部生成的结点），同时也成为当前的扩展结点（扩展结点是指正在产生孩子结点的结点）。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点

1. 用回溯法解题的一般步骤：

1. 针对给定的问题确定问题的解空间树，问题的解空间树应至少包含问题的一个解或者是最优解
2. 确定结点的扩展搜索规则
3. 以深度优先方式搜索解空间树，并在搜索过程中可以采用剪枝函数来避免无效搜索。其中，深度优先方式可以选择递归回溯或者迭代（非递归）回溯

1. 回溯法与深度优先遍历的异同

不同点：

1. 访问次序不同：

深度优先遍历的目的是“遍历”，本质是无序的，也就是说访问次序不重要，重要的是是否被访问过，因此再实现上只需要对每个位置记录是否被访问就足够了

回溯法的目的是“求解过程”，本质是有序的，也就是说必须每一步都是要求的次序，因此再实现上要使用访问状态来记录，也就是对于每个顶点记录已经访问过的邻居方向，回溯之后从新的未访问过的方向去访问其他邻居

1. 访问次数不同：

深度优先遍历对已经访问过的顶点不再访问，所有顶点仅访问一次

回溯法中已经访问过的顶点可能再次访问

1. 剪枝不同：

深度优先遍历不含剪枝

很多回溯法采用剪枝条件剪除不必要的分枝以提高效能

1. 求解0/1背包问题

第i层上的某个分枝结点的对应状态为dfs(i, tw, tv, rw, op)，其中tw表示装入背包中的物品总重量，tv表示背包中物品的总价值，rw表示考虑第i个物品时剩余物品的重量，op记录一个解向量

1. 选择第i个物品放入背包：op[i] = 1，如果放入物品i不超重，则tw = tw + w[i]，tv = tv + v[i]，rw = rw - w[i]，转向下一个状态dfs(i + 1, tw, tv, rw, op)，该决策对应左分枝
2. 不选择第i个物品放入背包：op[i] = 0，tw不变，tv不变，rw = rw - w[i]，转向下一个状态dfs(i + 1, tw, tv, rw, op)，该决策对应右分枝（tw + rw >= W时）

1. 求解复杂装载问题

有n个集装箱要装上两艘载重量分别为c1和c2的轮船

解：首先将第一艘轮船尽可能装满，然后将剩余的集装箱装在第二艘轮船上

1. 求解n皇后问题

使用回溯法：

1. 用数组q[]存放皇后的位置，(i, q[i])表示第i个皇后放置的位置，n皇后问题的一个解是(1, q[1])(2, q[2])...(n, q[n])，数组下标为0的元素不用
2. 先放置第一个皇后，然后依2、3、…、n的次序放置其他皇后，当第n个皇后放置好后产生一个解。为了找到所有解，此时算法还不能结束，继续试探第n个皇后的下一个位置
3. 第i（i < n）个皇后放置后，接着放置第i + 1个皇后，在试探第i + 1个皇后的位置时都是从第1列开始的
4. 当第i个皇后试探了所有列都不能放置时，则回溯到第i - 1个皇后，此时与第i - 1个皇后的位置(i - 1, q[i - 1])有关，如果第i - 1个皇后的列号小于n，即q[i - 1] < n，则将其移到下一列，继续试探；否则回溯到第i - 2个皇后，依此类推
5. 若第1个皇后的所有位置回溯完毕，则算法结束
6. 放置第i个皇后应与前面已经放置的i - 1个皇后不发生冲突

1. 求解图的m着色问题（求解任务分配问题）

对于每一个顶点，试探每一种着色（判断顶点与相邻顶点是否存在相同的着色），若可以着色，则进入下一个顶点着色，并进行回溯

1. 求解流水作业调度问题

有n个作业（编号为1-n）要在由两台机器M1和M2组成的流水线上完成加工，每个作业加工的顺序都是先在M1上加工，然后在M2上加工，M1和M2加工作业i所需的时间分别为ai和bi

采用回溯法进行求解：

用f1数组表示在M1上执行完当前作业i的总时间，用f2数组表示在M2上执行完当前作业i的总时间，对于排序树第i层的某个结点，若选择执行作业x[j]，显然其在M1上执行完的时间为f1 = f1 + a[x[j]]，考虑M2的时间可分为：

1. f2[i - 1] <= f1：说明该作业在M1上执行完后可以立即在M2上执行，不需要等待，它执行完的时间是f2[i] = f1 + b[x[j]]
2. f2[i?- 1] >?f1：说明在f1时刻M2上的前一个作业还没有执行完，此时该作业需要等待，等到前一个作业在M2上执行完后再执行完后在执行它，该作业在M2上执行完的时间是f2[i] = f2[i - 1] + b[x[j]]

所以f2[i] = max(f1 + b[x[j]], f2[i - 1] + b[x[j]])

剪枝条件：当第i层求出的f2[i]（即执行作业x[i]的总时间）已经大于大于bestf（当前求出的执行全部作业的最优总时间）时就没有必要从该结点向下扩展了，让其成为死结点

• 分枝限界法

1. 分枝限界法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法，但在一般情况下分枝限界法和回溯法的求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分枝限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解

2、

方法	解空间搜索方法	存储结点的数据结构	结点存储特性	常用应用
回溯法	深度优先	栈	活结点的所有可行子结点被遍历后才从栈中出栈	找出满足条件的所有解
分枝限界法	广度优先	队列、优先队列	每个结点只有一次成为活结点的机会	找出满足条件的一个解或者特定意义的最优解

3、设计合适的限界函数：

（1）一般先要确定问题解的特性，如果目标函数是求最大值，则设计上界限界函数ub（根节点的ub值通常大于或等于最优解的ub值），若si是sj的双亲结点，则应满足ub(si)>=ub(sj)，找到一个可行解ub(sk)后将所有小于ub(sk)的结点剪枝

（2）如果目标函数是求最小值，则设计下界限界函数lb（根节点的lb值一定要小于或等于最优解的lb值），若si是sj的双亲结点，则应满足lb(si)<=lb(sj)，找到一个可行解ub(sk)后将所有大于ub(sk)的结点剪枝

1. 求解步骤：

1. 队列式分枝限界法：

队列式分枝限界法将活结点表组织成一个队列，并按照队列先进先出原则选取下一个结点为扩展结点

1. 将根结点加入活结点队列
2. 从活结点队列中取出队头结点作为当前扩展结点
3. 对于当前扩展结点，先从左到右产生它的所有子节点，用约束条件检查，把所有满足约束条件的子节点加入活结点队列
4. 重复步骤（2）和（3），直到找到一个解或活结点队列为空为止

1. 优先队列式分枝限界法：

优先队列式分枝限界法的主要特点是将活结点表组成一个优先队列，并选取优先级最高的活结点作为当前扩展结点

1. 计算起始结点（根节点）的优先级并加入优先队列（与特定问题相关的信息的函数值决定优先级）
2. 从优先队列中取出优先级最高的结点作为当前扩展结点，使搜索朝着解空间树上可能由最优解的分枝推进，以便尽快地找出一个最优解
3. 对于当前扩展结点，先从左到右产生它的所有子节点，然后用约束条件检查，对所有满足约束条件的子结点计算优先级并加入优先队列
4. 重复步骤（2）和（3），直到找到一个解或活结点队列为空为止

在一般情况下，结点的优先级用与该结点相关的一个数值p来表示，如价值、费用、重量等。最大优先队列规定p值越大优先级越高，常用大根堆来实现；最小优先队列规定p值越小优先级越高，常用小根堆来实现

5、采用分枝限界法求解的关键问题：

（1）如何确定合适的限界函数

（2）如何组织待处理结点的活结点表

（3）如何确定解向量的各个分量

6、求解0/1背包问题

采用分枝限界法（采用上界设计方式）：

对于第i层的某个结点e，用e.w表示结点e已装入的总重量，用e.v表示已装入的总价值，如果所有剩余的物品都能装入背包，那么价值的上界e.ub显然是e.v + v[j](j = i + 1到n)；如果所有剩余的物品不能全部装入背包，假设物品i + 1到物品k能够全部装入，而物品k + 1只能装入一部分，那么价值的上界e.ub应是e.v + v[j](j = i + 1到n) + （物品k + 1装入的部分重量） * （物品k + 1的单位价值），这样每个结点实际装入背包的价值一定小于等于该上界

限界函数给出每一个可行结点相应的子树可能获得的最大价值的上界，如果这个上界不比当前最大值更大，则说明相应的子树中不含问题的最优解，因此该结点可以剪去（剪枝）

求解最优解的过程是先将求出上界的根节点进队，在队不空时循环：出队一个结点e，检查其左子结点并求出上界，若满足约束条件（e.w + w[e.i + 1] <= W），将其进队，否则该左子结点变成死结点；再检查其右子结点并求出其上界，若它是可行的（即其上界大于当前已找到可行解的最大总价值maxv，否则沿该结点搜索下去不可能找到一个更优的解），则将该右子结点进队，否则该右子结点被剪枝。循环这一过程，直到队列为空，算法最后输出最优解向量和最大总价值

在结点e进队时先判断是否为叶子结点（当e.i = n时为叶子结点），若是叶子结点，表示找到一个可行解，通过比较将最优解向量保存在bestx中，将最大总价值保存在maxv中，可行解对应的结点不进队，否则将结点进队

1. 求解图的单源最短路径：

给定一个带权有向图G = (V, E)，其中每条边的权是一个正整数，另外还给定V中的一个顶点v，成为源点。计算从源点到其他所有各顶点的最短路径长度，这里的长度是指路上各边权之和

解：

用dist数组存放从源点v出发的最短路径长度，dist[i]表示从源点v到顶点i的最短路径长度，初始时所有dist[i]值为∞

用prev数组存放最短路径，prev[i]表示从源点v到顶点i的最短路径中顶点i的前驱结点

采用广度优先遍历方法查找最短路径，在扩展顶点i时若顶点i到顶点j有边，剪枝的原则是如果结果这条边到达顶点j的路径长度更短（即dist[j]更小），则将顶点j作为子结点，否则不会将顶点j作为子结点，所有子结点进队

1. 求解流水作业调度问题

对于按1-n顺序执行的调度方案，f1数组表示在M1上执行完当前作业i的总时间，f2数组表示在M2上执行完当前作业i的总时间，计算公式如下：

f1 = f1 + a[i];

f2[i] = max(f1 + f2[i - 1]) + b[i];

对应结点e的lb的算法为：

void bound(NodeType &e) {

int sum = 0;

for(int i = 1; i <= n; ++i)

if(e.y[i] == 0)

sum += b[i];

e.lb = e.f1 + sum;

}

六、贪心法

1、贪心法的基本思路实在对问题求解时总是做出在当前看来是是最好的选择，也就是说贪心法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解，在求解问题时，通常求解问题直接给出或者可以分析出某些约束条件，满足约束条件的问题称为可行解。另外，求解问题直接给出或者可以分析出衡量可行解好坏的目标函数，使目标函数取最大（或最小）值的可行解称为最优解

1. 贪心法从问题的某一个初始空解出发，采用逐步构造最优解的方法向给定的目标前进，每一步决策产生n元组解(x0, x1, ..., xn-1)的一个分量，每一步用作决策依据的选择准则被称为最优量度标准（或贪心准则），也就是说，在选择解分量的过程中，添加新的解分量xk后，形成的部分解不违反可行解约束条件，每一次贪心选择都将所求问题简化为规模更小的子问题，并期望通过每次所做的局部最优选择产生出一个全局最优解

1. 使用贪心法求解的问题应具有的性质

1. 贪心选择性质
2. 最优子结构性质：即一个问题的最优解包含子问题的最优解

1. 贪心法的一般求解过程

1. 建立数学模型来描述问题
2. 把求解的问题分成若干个子问题
3. 对每一个子问题求解，得到子问题的局部最优解
4. 把子问题的局部最优解合成原来解问题的一个解

1. 求解田忌赛马问题

1）田忌最快的马比齐威王最快的马快，即a[righta] > b[rightb]，则二者比赛（两个最快的马比赛），田忌赢

2）田忌最快的马比齐威王最快的马慢，即a[righta] <?b[rightb]，则选择田忌最慢的马与齐威王最快的马比赛，田忌输

3）田忌最快的马与齐威王最快的马的速度相同，即a[righta] < b[rightb]

（1）田忌最慢的马比齐威王最慢的马快，即a[lefta] > b[leftb]，则两者比赛（两个最慢的马比赛），田忌赢

（2）田忌最慢的马比齐威王最慢的马慢，并且田忌最慢的马比齐威王最快的马慢，即a[lefta] < b[leftb]且a[lefta] < b[rightb]，则选择田忌最慢的马与齐威王最快的马比赛，田忌输

（3）其他情况，即a[righta] = b[rightb]且a[lefta] <= b[leftb]且a[lefta] >= b[rightb]，则a[lefta] >= b[rightb] = a[righta]，即a[lefta] = a[righta]，b[leftb] >= a[lefta] = b[rightb]，即b[leftb] = b[rightb]，说明比赛区间的所有马的速度全部相同，任何两匹马比赛都没有输赢

1. 求解流水作业调度问题

对于给定的作业(a, b)，当a <= b时让a比较小的作业尽可能先执行，否则让b比较小的作业尽可能后执行

• 动态规划

1. 动态规划通常基于一个递推公式及一个或多个初始状态，当前子问题的解将由上一次子问题的解推出

1. 相关概念

1. 一个图G=（V，E）是多段图，是指顶点集V划分成k各互不相交的子集Vi（1 <= i <= k），使得E中的任何一条边(u, v)必有u、v属于两个不同的子集Vi、Vj
2. 一个多段图分成若干个阶段，每个阶段用阶段变量k标识
3. 描述决策过程当前特征的量称为状态，它可以是数量，也可以是字符
4. 决策就是决策者在过程处于某一阶段的某一状态时面对下一阶段的状态做出的选择或决定
5. 策略就是策略者从第一阶段到最后阶段的全过程的决策构成的决策序列
6. 某一状态以及该状态下的决策与下一状态之间的指标函数之间的关系称为状态转移分成，其中指标函数是衡量对决策过程进行控制的效果的数量指标，可以是收益、成本或距离等

1. 动态规划求解的问题的性质：

1. 最优性原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优性原理
2. 无后效性：即某阶段的状态一旦确定，就不受这个状态以后决策的影响，也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关
3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到

1. 动态规划的设计步骤：

1. 划分阶段：按照问题的时间或空间特征把问题分为若干个阶段
2. 确定状态和状态变量：将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来
3. 确定决策并写出状态转移方程：根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程
4. 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件

1. 动态规划与其他方法的比较

1. 动态规划的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子问题，前一子问题的解为后一子问题的求解提供了有用的信息，但分治法中各个子问题是独立的（不重叠），动态规划适用于子问题重叠的情况，也就是各子问题包含公共的子问题
2. 动态规划方法又和贪心法有些相似，在动态规划中，可将一个问题的解决方案视为一系列决策的结果，不同的是，在贪心法中每采用一次贪心准则便做出了一个不可回溯的决策，还要考察每个最优决策序列中是否包含一个最优子序列
3. 一般采用动态规划求解问题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多

1. 求解整数拆分问题

求将正整数n无序拆分成最大数为k的拆分方案个数，所有的拆分方案不重复

使用动态规划，设f(n, k)为将数n无序拆分成最多不超过k个数之和（称为n的k拆分）的分方案个数：

1. 当n = 1或k = 1时显然f(n, k) = 1
2. 当n < k时有f(n, k) = f(n, n)
3. 当n = k时，其拆分方案有将n拆分成1个n的拆分方案，以及n的n - 1拆分方案，前者仅仅一种，所以有f(n, n) = f(n, n - 1) + 1
4. 当n > k时根据拆分方案中是否包含k可以分为两种情况：

①拆分中包含k的情况，即一部分为单个k，另一部分为{x1, x2, ..., xi}，后者的和为n - k，后者中可能再次出现k，因此是(n - k)的k拆分，所以这种拆分方案个数为f(n - k, k)

②拆分中不包含k的情况，则拆分中的所有拆分数都比k小，即n的(k - 1)拆分，拆分方案个数为f(n, k - 1)

因此，f(n, k) = f(n - k, k) + f(n, k - 1)

即：

1 当n = 1或者k = 1时

f(n, n) 当n < k时

f(n, k) = f(n, n - 1) + 1 当n = k时

f(n - k, k) + f(n, k - 1) 其他情况

1. 求解最大连续子序列和问题

dp[j]表示前j个元素中的最大连续子序列和

状态转移方程为：

dp[0] = 0 边界条件

dp[j] = max{dp[j - 1] + a[j], a[j]} 1 <= j <= n

1. 求解三角形最小路径问题

给定高度为n的一个整数三角形，找出从顶部到底部的最小路径和，注意从每个整数出发只能向下移动到相邻的整数

三角形采用二维数组a[0..n-1][0..n-1]存放，用二维数组dp[i][j]表示从顶部a[0][0]查找到(i, j)结点时的最小路径和，状态转移方程为：

dp[0][0] = a[0][0] 顶部边界

dp[i][0] = dp[i - 1][0] + a[i][0] 考虑第一列的边界，1 <= i <= n-1

dp[i][i] = dp[i - 1][i - 1] + a[i][i]; 考虑对角线的边界

其他有两条可达路径的结点

dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j]

1. 求解最长公共子序列问题

字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后形成的字符序列，给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列，该问题是求两序列A和B的最长公共子序列

采用动态规划，定义二维动态规划数组dp，其中dp[i][j]为子序列(a0, a1, ... ai-1)和(b0, b1, ..., bj-1)的最长公共子序列的长度，对应的状态转移方程为：

dp[i][j] = 0 i=0或j=0，边界条件

dp[i][j] = dp[i - 1][j - 1] + 1 a[i - 1] = b[j - 1]

dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) a[i - 1] ≠ b[j - 1]

1. 求解最长公共连续字串的长度

采用动态规划，对应的状态转移方程为：

dp[i][0] = 1 若s[i] == t[0]，初始化dp的第1列，0 <= i < n

dp[0][j] = 1 若s[0] == t[j]，初始化dp的第1行，0 <= j < m

dp[i][j] = dp[i - 1][j - 1] + 1 若s[i] == t[j]，1 <= i < n，1?<= j < m?????????????

1. 求解最长递增子序列问题

采用动态规划，dp[i]表示a[0...i]中以a[i]结尾的最长递增子序列的长度，对应的状态转移方程为：

dp[i] = 1 0 <= i <= n - 1

dp[i] = max(dp[i], dp[j] + 1) 若a[i] > a[j], 0<=i<=n-1, 0<=j<=i-1

1. 求解编辑距离问题

设A和B是两个字符串，现在要用最少的字符操作次数将字符串A转换为字符串B，字符操作有以下三种：

1. 删除一个字符
2. 插入一个字符
3. 将一个字符替换为另一个字符

采用动态规划，dp[i][j]表示a[1..i](1<=i<=m)与b[1..j](1<=j<=n)的最优编辑距离（即a[1..i]转换为b[1..j]的最少操作次数

1. 当B串空时，要删除A中的全部字符转换为B，即dp[i][0] = i
2. 当A串空时，要再A中插入B的全部字符转换为B，即dp[0][j] = j
3. 对于非空的情况，当a[i - 1] = b[j - 1]，这两个字符不需要任何操作，即dp[i][j] = dp[i - 1][j - 1]
4. 当a[i - 1] != b[j - 1]是，有以下三种情况

1. 将a[i - 1]替换为b[j - 1]，有dp[i][j] = dp[i - 1][j - 1] + 1
2. 在a[i - 1]字符后面插入b[j - 1]字符，有dp[i][j] = dp[i][j-1] + 1
3. 删除a[i - 1]字符，有dp[i][j] = dp[i - 1][j] + 1

故状态转移方程为：

dp[i][j] = dp[i - 1][j - 1] 当a[i - 1] = b[j - 1]时

当a[i - 1] ≠ b[j - 1]时

dp[i][j] = min(dp[i - 1][j - 1] + 1, d[i][j - 1] + 1, dp[i - 1][j] + 1)

1. 求解0/1背包问题

采用动态规划，dp[i][r]表示背包剩余容量为r(1 <= r <= W)，已考虑物品1、2、…、i(1 <= i <= n)时背包装入物品的最优价值，对应的状态转移方程为：

dp[i][0] = 0（背包不能装入任何物品，总价值为0）

dp[0][r] = 0（没有任何物品可装入，总价值为0）

dp[i][r] = dp[i - 1][r]（当r < w[i]时物品i放不下）

在放入和不放入之间选择最优解

dp[i][r] = max(dp[i - 1][r], dp[i - 1][r - w[i]] + v[i])

1. 求解完全背包问题

有n种重量和价值分别为wi、vi（0 <= i < n）的物品，从这些物品种挑选出总重量不超过W的物品，求出挑选物品价值综合最大的方案，每种物品可以挑选任意多件

采用动态规划，dp[i][j]表示从前i个物品种选出重量不超过j的物品的最大总价值，对应的状态转移方程为：

dp[i][0] = 0（背包不能装入任何物品，总价值为0）

dp[0][r] = 0（没有任何物品可装入，总价值为0）

dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i])

fk[i][j] = k（物品i取k件）

或者：

dp[i][j] = dp[i - 1][j]（当j < w[i]时物品i放不下）

在放入和不放入之间选择最优解

dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])

1. 求解资源分配问题

某公司有三个商店A、B、C，将新招聘的五名员工分配给这三个商店，各商店得到新员工后每年的盈利情况如表，求分配给各商店各多少员工才能使公式的盈利最大？

采用动态规划，dp[i][s]表示考虑商店i-商店m并分配总共s个人后的最优盈利，pnum[i][s]表示求出dp[i][s]时对应商店i的分配人数，v[i][j]表示商店i有j各员工时的盈利情况，状态转移方程为：

dp[m + 1][j] = 0

// pnum[i][s] = dp[i][s]取最大值的j(0 <= j <= n)

dp[i][s] = max(v[i][j] + dp[i + 1][s - j])

显然dp[1][n]为最优盈利