动态规划的主要思想是：从（精心选择）较小规模子问题的最优解中建立问题的最优解。 子问题的选择允许递归构造子问题的最优解，从最优解到较小规模的子问题。 DP的效率来自于这样一个事实，即解决较大问题所需的子问题集严重重叠；每个子问题只求解一次，其解被存储在一个表中，以供解决较大问题时使用。
实例：活动ai的列表，1≤i≤n，开始时间si，结束时间fi。两个活动不能同时进行。 任务：找出总持续时间最长的兼容活动的子集。
我们在上一节使用贪心方法来解决一个有点类似的问题，即找到具有最大可能数量的兼容活动的子集，但是贪婪方法不适用于当前的问题。
我们首先根据完成时间将这些活动排序为一个非递减序列，因此假设f1≤f2≤…≤fn。 对于每个i≤n，我们解决以下子问题：
子问题P（i）：求出活动序列Si =⟨a1，a2，…，ai⟩的子序列σi使得：
σi包括非重叠活动；σi以活动ai结尾；σi在所有满足1和2的Si序列中具有最大总持续时间。 注意：2的作用是简化递归。令T（i）为子问题P（i）的最优解S（i）的总持续时间。 对于S（1），我们选择a1；因此T（1）= f1- s1;
递归：假设我们已经解决了所有j <i和 将它们存储在表格中：
在表中，除了T(i)，我们还存储了达到上述最大值的j。
为什么这样的递归会获得最优解P(i)？
设P(i)=(ak1,ak2…ak(m-1),akm), km=i.
我们称：被截取的子序列S′=（ak1，ak2，akm−1）是最佳 子问题P（km−1）的解，其中km−1<i。
我们使用“剪贴”方式（曾证明贪婪解的最优性）！
如果序列S ∗的总持续时间大于序列S’的持续时间，并且也以活动akm-1结尾，则可以通过用活动akm扩展序列S ∗获得序列S^ 并获得总持续时间比序列S的总持续时间更长的子问题P（i）的解，这与S的最优性相矛盾。
因此，从最优解S=（ak1，ak2，…akm-1）获得问题P（i）（= P（akm））的最优解S =（ak1，ak2，…，akm-1，akm）,通过将其扩展为akm来解决问题P（akm-1）.
我们让Tmax=max{T(i):I<=n}.
我们现在可以从部分解的表中重建解决问题的最优序列，因为在表的第i个槽中，除了T（i），我们还存储了j，使得P（i）的最优解扩展了子问题P（j）的最优解。
为什么这样的解是最优的，即为什么要寻找必须以ai结尾的P（i）的最优解，却不会导致我们在没有这样的额外要求的情况下错过最优解？
考虑没有此类额外要求的最佳解决方案，并假设其以活动ak结束；那么它将作为问题P（k）的最优解而获得。
时间复杂度：按照活动的结束时间O（nlogn）对活动进行排序，对于以ai结尾的解决方案，我们需要解决n个子问题P（i）；对于每个这样的间隔，我们必须找到所有先前兼容的间隔及其最佳解决方案（将在表中查找）。因此，时间复杂度为O（n2）。
最长递增子序列：给定n个实数A [1…n]的序列，确定一个值严格增加的子序列中具有最大长度的序列（不一定是连续的）。
解决方案：对于每个i≤n，我们解决以下子问题：
子问题P（i）：找到最大长度的序列A [1…i]的后续序列，其中值严格增加，并以A [i]结尾。
递归：假设我们已经解决了j <i的所有子问题；
现在，我们寻找所有A [m]，使得m <i且A [m] <A [i]；
在这些中，我们选择m产生最长的递增子序列，以A [m]结尾，并将其扩展为A [i]，以获得最长的递子增序列，其结尾为A [i]；
为什么这会为子问题提供最佳解决方案？“剪切和粘贴”方法。
P（i）的分段的最优解必须产生子问题P（m）的最优解，否则，通过扩展P（m）的最优解，我们也可以找到更好的P（i）的解。
我们在表的第i个槽中存储最长的递增子长度（以A [i]和m结尾）的长度，以使P（i）的最优解扩展P（m）的最优解。
因此，我们发现对于每i≤n，以A [i]结尾的序列A [1…i]的最长递增后续序列。
最后，从所有此类序列中选择最长的序列。
同样，序列以A [i]结束的条件不是限制性的，因为如果最佳解以某个A [m]结束，它将被构造为P（m）的解。
时间复杂度：O(n^2) 练习：（有些困难，但非常有用）的设计和算法 解决此问题，时间为n log n。
换零钱问题。您会得到n种价值的硬币面额 v（1）<v（2）<… <v（n）（所有整数）。假设v（1）= 1，那么您始终可以对任何整数兑换。给出一种算法，该算法使用任意数量的硬币来对任何给定的整数C进行兑换，并假设每种面额的硬币数量不受限制。
解决方案：对数量C进行DP递归。我们将填充一个包含C个空缺的表，以便将数量i的最佳解决方案存储在空缺i中。
如果C=1，则解是微不足道的：只需使用一枚面额为v（1）=1的硬币；
假设我们已经找到了每一个j<i的最优解，找到数量i的最优解。
如果C=1，则解是微不足道的：只需使用一枚面额为v（1）=1的硬币；
假设我们已经找到了每一个j<i的最优解，现在我们要找到总数i的最优解。
我们考虑最优解决方案opt（i−v（k）），形式是i−v（k），其中k的范围从1到n（v（1），…，v（n）是所有可用的面额。）。
在所有这些最优解中（我们在递归构造的表中找到了）我们选择使用最少数量硬币的一个，假设这是一些m的opt（i−v（m）），1≤m≤n。 我们通过在opt（i−v（m））上添加一枚面额为v（m）的硬币，得到数量i的最优解opt（i）。 为什么这会产生i≤C的最优解？ 考虑总数i≤C的最优解决方案；并且假设该解决方案包括至少一种面值为v（m）的硬币（对于某些1≤m≤n）。但是，移除此类硬币必须产生总数的最优解i−v（m）（再次通过我们的剪切-粘贴理论验证）。
然而，我们不知道最优解包括哪些硬币，因此我们尝试所有可用的硬币，然后选择m，对于数量i−v（m）的最优解决方案使用最少的硬币。
在表的第i个空缺中存储m和opt（i）就足够了，因为这允许我们通过查看存储在第i个空缺中的m1，然后查看存储在空缺i−v（m1）中的m2，然后查看存储在空缺i−v（m1）−v（m2）中的m2，依此类推。
最终，经过C的许多此类步骤，我们获得了opt（C），这是我们需要的解决方案。
时间复杂度是nC。
注意：我们的算法不是输入长度的多项式时间算法，因为C的表示形式的长度仅为log C，而运行时间为nC
**整数背包问题（允许重复的物品）**所有类型为i的物品都是相同的，重量为wi，价值为vi。您还拥有容量为C的背包。选择所有适合放在背包中且其值尽可能大的可用物品的组合。您可以带任何数量的任何种类的物品。
解决方案：DP在背包容量C上递归。
我们为i≤C的所有容量背包建立了最佳解决方案表。
假设我们已经解决了所有容量j <i的背包的问题。
现在我们来看所有背包的最优解opt（i-wm）或所有1≤m≤n的容量i − wm；
选择opt（i-wm）+ vm最大的那个。
将大小为i-wm的背包添加到这样的最优解中，以获得大小为i的背包的包装，该背包的最大价值。
因此，opt(i) = max{opt(i−wm)+vm : 1 ≤ m ≤ n}. 经过C的许多步骤，我们获得了我们需要的opt（C）。
同样，此算法不是多项式长度的。
**整数背包问题（不允许重复物品）**你有n个物品（其中一些物品可以是相同的）；物品Ii的重量为wi，价值为vi。你还有一个容量为C的背包。选择一个可供选择的物品组合，这些物品都能放在背包中，并且其价值尽可能大。
这是一个“2D”递归的例子；我们将逐行填充一个大小为n×C的表；所有i≤n和C≤C的子问题P（i，C）的形式如下：
从项目I1、I2…Ii选择装在容量为c的背包中且总价值最大的子集。
现在修正i≤n和c≤c，并假设我们已经解决了以下子问题： 1.所有j<i和所有容量从1到C的背包. 2.对于我来说，我们已经解决了所有容量d<c的问题。
我们现在有两个选择：要么接受第二项，要么不接受；
所以我们看opt（i−1，c−wi）和opt（i−1，c）哪个是最优解。
平衡分区问题 有一组n个整数。将这些整数分成两个子集，使| S1−S2 |最小化，其中S1和S2表示两个子集中每个元素的和。
解：设集合中所有整数的总和，考虑背包大小问题（不允许重复项），背包大小S／2，每一个整数xi的大小和值均等于xi。
声明：最佳的背包产生最好的平衡分割，S1是背包中的所有整数，S2是背包外的所有整数。
实例：两条带有工作站的流水线，用于n个工作。
在第一条装配线上，第k个作业需要a(1，k)（1≤k≤n）的时间单位为 完成;在第二条装配线上，同一作业需要a（2，k）个单位的时间。
将产品从第一条装配线上的工位k-1移至工位k 在第二行上花费t（1，k-1）个单位时间。
同样，将产品从第二条装配线上的工位k-1移动到第一条装配线上的工位k，需要t（2，k-1）个单位时间。
要将未完成的产品带到第一条装配线，需要花费e1单位时间。
要将未完成的产品带到第二条装配线，需要花费e2单位时间。
为了将成品从第一条装配线运送到仓库，需要花费x1单位时间。
为了将成品从第二条组装线运送到仓库，需要x2单位。
任务：找出必要时使用两条生产线组装产品的最快方法。 对于每个k≤n，我们通过对k进行同时递归来求解子问题P（1，k）和P（2，k）：
P（1，k）：求出完成前k个作业所需的最小时间m（1，k），以使第k个作业在第一条装配线上的第k个工作站上完成；
P（2，k）：找到完成第一个k所需的最小时间m（2，k），在第二条装配线的第k个工作站上完成了第k个作业。
对于任意大小的3个矩阵，我们有A(BC)=(AB)C. 然而，为了得到矩阵乘积，需要执行的实数乘法的次数不同。 A=10100，B=1005，C=5*50 问题实例：一系列矩阵A1，A2 … An;
任务：将它们分组以使查找乘积矩阵所需的乘法总数最小。
不同括号分布的总数等于n个叶子的二叉树数量。 因此，我们不能彻底搜索括号的最佳位置，因为是多项式时间，所以我们要找到一个更快的算法。 要考虑的子问题P（i，j）是： “矩阵分组成AiAi+1…Aj−1Aj，以尽可能减少找到乘积矩阵所需的乘法总数”。 注意：这看起来是一个“二维递归”的例子（因为需要i和j），但实际上我们可以用一个简单的“线性”递归来实现。
我们将这些子问题按j−i的值分组，并对j−i的值执行递归。
在每个递归步骤m中，我们求解j−i=m的所有子问题P（i，j）。
设m（i，j）表示计算乘积AiAi+1…Aj−1Aj所需的最小乘法次数；也让矩阵Ai的大小设为s（i−1）×s（i）。
递归：我们研究了所有可能的方式来设置最主要（最外的）的乘法，将链分成乘积（Ai … Ak）·（Ak + 1 … Aj）。
注意，k-i <j-i和j-（k +1）<j-i；因此，我们已经有了子问题P（i，k）和P（k + 1，j）的解，它们已经计算并存储在空缺k-i和 j-（k +1），分别在空缺j-i之前填充。
还要注意，矩阵乘积Ai … Ak是s（i − 1）×sk矩阵L，而Ak + 1 … Aj是sk×sj矩阵R。
为了将s（i − 1）×sk矩阵L和sk×sj矩阵R相乘，需要s（i − 1）sksj多次乘法：
注意，递归步骤是蛮力搜索，但是整个算法不是，因为所有子问题只被求解了一次，并且只有O（n^2）个子问题。
可以存储为获得m（i，j）的递归定义中的最小值的k，以检索整个链A1 … An的括号的最佳位置。
因此，在表的第m个空缺中，我们存储j-i = m的所有组合（m（i，j），k）。
假设我们要比较符号S和S ∗的两个序列的相似程度。
例如：两种病毒的遗传密码有多相似。
这可以告诉我们一个病毒是否仅仅是另一个的遗传突变。
如果可以通过删除S的某些符号（同时保留其余符号的顺序）获得s，则序列s是另一个序列S的子序列。
给定两个序列S和S*序列，如果s是S和S ∗的公共子序列，并且长度最大，则s是S的最长公共子序列。
假设两个序列S = ⟨a1,a2,…an⟩ ， S∗ = ⟨b1,b2,…,bm⟩， 求出S，S ∗的最长公共序列。
我们首先找到S，S ∗的最长公共子序列的长度。
“2D递归”：对于所有1≤i≤n和所有1≤j≤m，令c [i，j]为截短序列Si = ⟨a1,a2,…ai⟩ 和 Sj∗ = ⟨b1,b2,…,bj⟩的最长公共子序列的长度。
递归：我们逐行填充表格，因此子问题的顺序为字典顺序； 如果我们找三个序列S1，S2，S3的最长公共子序列，该怎么办？ 我们可以LCS(LCS(S1,S2),S3)嘛? 不可以！ 解决方法： 设S = ⟨a1,a2,…an⟩, S∗ = ⟨b1,b2,…,bm⟩ and S∗∗ = ⟨c1,c2,…,ck⟩. 任务：找到S, S∗, S∗∗的最长公共子序列。 我们再次首先找到S，S ∗，S ∗∗的最长公共子序列的长度。 对于所有1≤i≤n，所有1≤j≤m且所有l≤k，令d [i，j，l]为截短序列中最长的公共子序列对于Si = ⟨a1 , a2 , . . . ai ⟩，S∗ = ⟨b1,b2,…,bj⟩和S∗∗ = ⟨c1,c2,…,cl⟩。
三个序列S=⟨a1，a2，…an⟩，S⟨b1，b2，…，bm⟩和S⟨c1，c2，…，ck⟩。 求S，S∗，S∗∗的最长公共子序列。
任务：求S，S的最短公共超序列S，即最短可能的序列S使得S和S都是S的子序列。
求s和s*的最长公共子序列LCS（s，s∗），然后按任意顺序在正确的位置添加两个序列的不同元素；例如： s =abacada s∗ =xbycazd LCS(s, s∗) =bcad shortest super-sequence S =axbyacazda
编辑距离给定长度为n的两个文本字符串A和长度为m的B，您希望将A转换为B。您可以插入一个字符，删除一个字符，并用另一个字符替换一个字符。插入成本cI、删除成本cD和更换成本cR。 任务：找出总成本最低的A到B的转换。
注意：如果所有操作都有一个单位成本，那么您需要寻找将a转换为B所需的最少数量的此类操作；这个数字称为a和B之间的编辑距离。
如果序列是DNA碱基的序列，并且成本反映了相应突变的概率，那么最小成本表示这两个序列之间的密切关系。
子问题：设C（i，j）是将序列A[1…i]转换为序列B[1…j]的最小代价，对于所有i≤n和所有j≤m。
子问题P（i，j）：在所有i≤n和所有j≤m的情况下，求将序列A[1…i]转换为序列B[1…j]的最小代价C（i，j）。
实例：例如，一个数字序列，其中有运算+、-、×，比如1+2−3×6−1−2×3−5×7+2−8×9。 任务：以使结果表达式具有最大可能值的方式放置方括号。 子问题是什么？ 也许对于一个数的子序列a[i…j]放上括号以便得到的表达式最大化？ 也许我们可以考虑哪些是主要的操作，即。 A[i…k]⊙A[k+1…j]。这里⊙是A[k]和A[k+1]之间的任何运算。 但是，如果A[i…k]和A[k+1…j]同时存在正值和负值，这种表达式何时才能最大化呢？？ 也许我们应该寻找括号的位置不仅是最大值，而且是最小值！
实例：你得到了n只海龟，每只海龟你都得到了它的重量和力量。乌龟的力量是你能给它施加的最大重量，而不会使它的壳裂开。
任务：找到尽可能多的海龟，你可以一个一个叠在另一个上面，而不会弄坏任何海龟。
提示：按照海龟的重量和强度的总和的递增顺序来订购海龟，并通过递归进行排序。
实例：有向加权图G=（V，E），其权重可以是 负的，但没有负的总重量和一个顶点s∈V的环。
目标：找到从顶点s到其他顶点t的最短路径。
解决方案：由于没有负重量的环，因此最短路径不能包含环，因为可以切除一个环以产生较短的路径。
因此，每条最短的路径最多可以具有| V |-1条边。
子问题：对于每个v∈V和每个i，（1≤i≤n-1），令opt（i，v）为 从s到v的最短路径的长度，最多包含i条边。
我们的目标是为每个顶点t∈G找到opt（n−1，t）的值和 达到这种长度的路径。
注意，如果从顶点v到t的最短路径是（v，p1，p2，…，pk，t），那么（p1，p2，…，pk，t）必须是从p1到t的最短路径，（v，p1，p2，…，pk）也必须是从v到pk的最短路径。
用opt（i，v）表示所有至多包含i条边的路径中从s到v的最短路径的长度，并让pred（i，v）是该最短路径上顶点v的直接前身。 计算opt（i，v）需要时间O（| v | |* | E |），因为i ≤ |V | − 1且对于每个v，min取所有入到v的边e（p，v）；因此，在每一轮中，所有边都被检查。
算法产生从s到图中每个顶点的最短路径。
所采用的方法有时被称为“松弛”，因为我们逐步放宽了对最短路径可以包含多少条边的附加约束。
再次使G =（V，E）为有向加权图，其中V = {v1，v2，…，vn}，权重w（e（vp，vq））或边e（vp，vq）为负，但没有带负的权重的环。
我们可以使用某种类似的想法来获得从每个顶点vp到每个顶点vq（包括返回vp）的最短路径。
令opt（k，vp，vq）是从顶点vp到顶点vq的最短路径的长度，以使所有中间顶点都在顶点{v1，v2，…，vk}之间，（1≤k≤n ）。
因此，我们逐渐放宽了中间顶点必须属于{v1，v2，…，vk}的约束。 算法运行时间|V|^3。
计算正整数n的分区，也就是说正整数的不同集合{n1。，nk}加起来等于n，即n1+…+nk=n。
提示：让nump（i，j）表示分区{j1,…,jp}，即j1+…+jp=j，另外，它还具有每个分区的每个元素jq满足jq≤i的性质。我们正在寻找nump（n，n），但递归是基于所有i，j≤n的j部分的允许大小i的松弛。为了得到nump（i，j）的递归定义，区分所有组件都≤i的分区的情况−1以及至少有一个部件的尺寸为i。
Comp9101 week5 lecture
