第9讲 深搜与简单的动态规划

动态规划的基本原理和基本应用动态规划（Dynamic Programming）是一种通过将一个问题分解为较小的子问题并存储子问题的解来解决复杂问题的方法。

动态规划的基本原理是通过记忆化或自底向上的迭代方式来求解问题，以减少不必要的重复计算。

它在计算机科学和数学中具有广泛的应用，尤其是在优化、组合数学和操作研究等领域。

1.确定最优子结构：将原问题分解为较小的子问题，并且子问题的最优解能够推导出原问题的最优解。

2.定义状态：确定存储子问题解的状态变量和状态方程。

3.确定边界条件：确定初始子问题的解，也称为边界状态。

4.递推计算：利用状态方程将子问题的解计算出来，并存储在状态变量中。

5.求解最优解：通过遍历状态变量找到最优解。

1.背包问题：背包问题是动态规划的经典应用之一、它有多种变体，其中最基本的是0/1背包问题，即在限定容量的背包中选择物品，使得所选物品的总价值最大。

可以使用动态规划的思想来解决背包问题，确定状态为背包容量和可选物品，递推计算每个状态下的最优解。

2. 最长递增子序列：最长递增子序列（Longest Increasing Subsequence）是一种常见的子序列问题。

给定一个序列，找到其中最长的递增子序列。

可以使用动态规划来解决这个问题，状态可以定义为以第i个元素为结尾的最长递增子序列的长度，并递推计算每个状态的解。

3.矩阵链乘法：矩阵链乘法是一种优化矩阵连乘计算的方法。

给定一系列矩阵，求解它们相乘的最小计算次数。

可以使用动态规划解决矩阵链乘法问题，状态可以定义为矩阵链的起始和结束位置，递推计算每个状态下最小计算次数。

4.最短路径问题：最短路径问题是在有向图或无向图中找到两个节点之间最短路径的问题。

可以使用动态规划解决最短路径问题，状态可以定义为起始节点到一些节点的最短距离，递推计算每个状态的最优解。

动态规划算法
动态规划算法（Dynamic Programming）是一种解决多阶段最优化决策问题的算法。

它将问题分为若干个阶段，并按照顺序从第一阶段开始逐步求解，通过每一阶段的最优解得到下一阶段的最优解，直到求解出整个问题的最优解。

动态规划算法的核心思想是将问题划分为子问题，并保存已经解决过的子问题的解，以便在求解其他子问题时不需要重新计算，而是直接使用已有的计算结果。

即动态规划算法采用自底向上的递推方式进行求解，通过计算并保存子问题的最优解，最终得到整个问题的最优解。

动态规划算法的主要步骤如下：
1. 划分子问题：将原问题划分为若干个子问题，并找到问题之间的递推关系。

2. 初始化：根据问题的特点和递推关系，初始化子问题的初始解。

3. 递推求解：按照子问题的递推关系，从初始解逐步求解子问题的最优解，直到求解出整个问题的最优解。

4. 得到最优解：根据子问题的最优解，逐步推导出整个问题的最优解。

5. 保存中间结果：为了避免重复计算，动态规划算法通常会使
用一个数组或表格来保存已经求解过的子问题的解。

动态规划算法常用于解决最优化问题，例如背包问题、最长公共子序列问题、最短路径问题等。

它能够通过将问题划分为若干个子问题，并通过保存已经解决过的子问题的解，从而大大减少计算量，提高算法的效率。

总之，动态规划算法是一种解决多阶段最优化决策问题的算法，它通过将问题划分为子问题，并保存已经解决过的子问题的解，以便在求解其他子问题时不需要重新计算，从而得到整个问题的最优解。

动态规划算法能够提高算法的效率，是解决最优化问题的重要方法。

动态规划与搜索——动态规划是高效率、高消费算法同样是解决最优化问题，有的题目我们采用动态规划，而有的题目我们则需要用搜索。

这其中有没有什么规则呢？我们知道，撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是“万能”的。

所以动态规划可以解决的问题，搜索也一定可以解决。

把一个动态规划算法改写成搜索是非常方便的，状态转移方程、规划方程以及边界条件都可以直接“移植”，所不同的只是求解顺序。

动态规划是自底向上的递推求解，而搜索则是自顶向下的递归求解（这里指深度搜索，宽度搜索类似）。

反过来，我们也可以把搜索算法改写成动态规划。

状态空间搜索实际上是对隐式图中的点进行枚举，这种枚举是自顶向下的。

如果把枚举的顺序反过来，变成自底向上，那么就成了动态规划。

(当然这里有个条件，即隐式图中的点是可排序的)正因为动态规划和搜索有着求解顺序上的不同，这也造成了它们时间效率上的差别。

在搜索中，往往会出现下面的情况：对于上图(a)这样几个状态构成的一个隐式图，用搜索算法就会出现重复，如上图(b)所示，状态c2被搜索了两次。

在深度搜索中，这样的重复会引起以c2为根整个的整个子搜索树的重复搜索；在宽度搜索中，虽然这样的重复可以立即被排除，但是其时间代价也是不小的。

而动态规划就没有这个问题，如上图(c)所示。

一般说来，动态规划算法在时间效率上的优势是搜索无法比拟的。

（当然对于某些题目，根本不会出现状态的重复，这样搜索和动态规划的速度就没有差别了。

）而从理论上讲，任何拓扑有序（现实中这个条件常常可以满足）的隐式图中的搜索算法都可以改写成动态规划。

但事实上，在很多情况下我们仍然不得不采用搜索算法。

那么，动态规划算法在实现上还有什么障碍吗？考虑上图(a)所示的隐式图，其中存在两个从初始状态无法达到的状态。

在搜索算法中，这样的两个状态就不被考虑了，如上图(b)所示。

但是动态规划由于是自底向上求解，所以就无法估计到这一点，因而遍历了全部的状态，如上图(c)所示。

动态规划问题动态规划（Dynamic Programming）是一种通过拆分问题为较小子问题来解决复杂问题的算法思想。

在计算机科学中，动态规划经常被用于最优化问题。

动态规划的基本思想动态规划通常用于解决具有重叠子问题和最优子结构的问题。

重叠子问题意味着问题可以被分解为多个重叠子问题，而最优子结构意味着问题的最优解可以通过子问题的最优解来计算。

动态规划的基本思想是将大问题分解为小问题，并依次求解小问题的最优解，然后将这些最优解组合起来得到大问题的最优解。

在动态规划的过程中，通常会使用表格或数组来保存子问题的计算结果，以便在下一次遇到相同子问题时直接查表得出最优解。

动态规划的应用动态规划广泛应用于诸如优化、序列匹配、最短路径等领域。

以下是一些典型应用场景：•背包问题：给定一个背包容量和一组物品，每个物品有自己的价值和重量，求解如何在不超过背包容量的情况下使得装入背包的物品价值最大化。

•最长公共子序列：给定两个序列，求解这两个序列最长的公共子序列的长度。

•最短路径问题：求解两点之间的最短路径，例如Dijkstra算法和Floyd算法都是动态规划的应用。

•最长递增子序列：给定一个序列，求解其中一个递增子序列的最大长度。

•编辑距离问题：求解将一个字符串转换成另一个字符串的最小操作次数，包括删除、插入、替换操作。

•区间调度问题：给定一组活动的起止时间，求解在不重叠的情况下能参加的最多活动数量。

动态规划的问题特征动态规划问题通常具有以下特征：1.最优子结构：问题的最优解可以通过子问题的最优解来递推求解。

2.重叠子问题：问题可以被分解为多个重叠的子问题，这些子问题可以共享相同的解。

3.状态转移方程：问题可以通过状态之间的转移关系来描述，通常采用递推式或递归的方式定义状态转移方程。

4.基本案例：问题需要定义基本情况，也称为递归的终止条件。

动态规划的解题步骤解决动态规划问题通常需要遵循以下步骤：1.定义状态：明确问题的状态，通常需要定义一个状态数组或矩阵来表示问题的状态。

动态规划求解方法动态规划(Dynamic Programming)是一种常见的求解优化问题的方法，它通过将问题分解成更小的子问题，并保存子问题的解来降低时间复杂度。

动态规划通常使用一个表格来记录子问题的解，然后根据递推关系计算出更大问题的解。

动态规划的求解方法一般包含以下几个步骤：1.定义问题：首先，需要明确要解决的问题是什么。

动态规划通常适用于求解具有最优子结构性质的问题，即原问题的最优解可以通过一系列子问题的最优解得到。

2.确定状态：接下来，需要确定动态规划的状态。

状态是问题中会变化的量，它包含了问题的关键信息。

在动态规划中，状态可以是一个或多个变量。

3.建立转移方程：然后，需要建立问题的转移方程。

转移方程描述了问题状态之间的关系，用来计算子问题的最优解。

转移方程可以通过观察问题的特点或者使用递推关系得到。

4.确定初始条件：接下来，需要确定边界条件或初始条件。

边界条件是问题中的一些特殊情况，它们通常是一些最小子问题的解。

初始条件是指将边界条件中的解赋值给表格中对应的位置。

5.使用递推关系计算：最后，使用递推关系将表格中的其他位置的解计算出来。

通常，可以使用自底向上的方法，从表格的第一个位置开始计算，依次填充整个表格。

动态规划的优点在于它可以将一个复杂的问题分解成多个子问题，然后通过记录子问题的解来减少重复计算。

这样，可以大大提高求解问题的效率。

动态规划通常适用于求解满足最优化原理和无后效性条件的问题。

最优化原理是指问题的最优解具有递归的结构，即解可以通过子问题的最优解得到。

无后效性条件是指问题的当前状态决定了未来的决策，与过去的决策无关。

动态规划在算法设计和实现中有很多经典的应用，例如最长公共子序列问题、0/1背包问题、最短路径问题等。

下面简要介绍其中的两个经典应用。

1.最长公共子序列问题：给定两个字符串s1和s2，求它们的最长公共子序列。

最长公共子序列是指在两个字符串中以相同的顺序出现的最长的子序列。

动态规划与搜索——动态规划是高效率、高消费算法同样是解决最优化问题，有的题目我们采用动态规划，而有的题目我们则需要用搜索。

这其中有没有什么规则呢？我们知道，撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是“万能”的。

所以动态规划可以解决的问题，搜索也一定可以解决。

把一个动态规划算法改写成搜索是非常方便的，状态转移方程、规划方程以及边界条件都可以直接“移植”，所不同的只是求解顺序。

动态规划是自底向上的递推求解，而搜索则是自顶向下的递归求解（这里指深度搜索，宽度搜索类似）。

反过来，我们也可以把搜索算法改写成动态规划。

状态空间搜索实际上是对隐式图中的点进行枚举，这种枚举是自顶向下的。

如果把枚举的顺序反过来，变成自底向上，那么就成了动态规划。

(当然这里有个条件，即隐式图中的点是可排序的)正因为动态规划和搜索有着求解顺序上的不同，这也造成了它们时间效率上的差别。

在搜索中，往往会出现下面的情况：对于上图(a)这样几个状态构成的一个隐式图，用搜索算法就会出现重复，如上图(b)所示，状态C2被搜索了两次。

在深度搜索中，这样的重复会引起以C2为根整个的整个子搜索树的重复搜索；在宽度搜索中，虽然这样的重复可以立即被排除，但是其时间代价也是不小的。

而动态规划就没有这个问题，如上图(c)所示。

一般说来，动态规划算法在时间效率上的优势是搜索无法比拟的。

（当然对于某些题目，根本不会出现状态的重复，这样搜索和动态规划的速度就没有差别了。

）而从理论上讲，任何拓扑有序（现实中这个条件常常可以满足）的隐式图中的搜索算法都可以改写成动态规划。

但事实上，在很多情况下我们仍然不得不采用搜索算法。

那么，动态规划算法在实现上还有什么障碍吗？考虑上图(a)所示的隐式图，其中存在两个从初始状态无法达到的状态。

在搜索算法中，这样的两个状态就不被考虑了，如上图(b)所示。

但是动态规划由于是自底向上求解，所以就无法估计到这一点，因而遍历了全部的状态，如上图(c)所示。

动态规划的基本原理和基本应用
一、动态规划的基本原理
动态规划（Dynamic Programming）是一种运用在运筹学中的一种数
学规划方法。

它的基本思路是：将一个复杂的求解问题分解成若干个更简
单的子问题，再从这些子问题出发，求出各子问题的解，回溯到原问题求
出原问题的解，通常情况下，动态规划的核心是对于每一个子问题只求解
一次，存储子问题的解，避免了重复求解子问题。

1.最优子结构性质：具有最优子结构性质的问题可以用动态规划求解，即如果一些问题的求解最优解由其子问题的最优解组合而成，那么该问题
也是最优的；
2.重复子问题性质：具有重复子问题性质的问题可以用动态规划求解，即一些问题的解可以由重复的子问题的解组合而成；
3.边界条件：求解动态规划的问题要求有边界条件，即知道求解问题
的初始和终止条件；
4.最优化原理：即求解问题的全局最优解可以由求子问题的最优解组
合而成，求解问题从最优解的最终状态开始，逐渐迭代至初始状态；
5.无后效性：即状态仅取决于其之前的几个状态，不受其之后状态的
影响。

二、动态规划的基本应用
1.适用于短路径问题：在交通运输、通信网络中。

动态规划和记忆化搜索一些理解动态规划：就是一个最优化问题，先将问题分解为子问题，并且对于这些分解的自问题自身就是最优的才能在这个基础上得出我们要解决的问题的最优方案，要不然的话就能找到一个更优的解来替代这个解，得出新的最优自问题，这当然是和前提是矛盾的。

动态规划不同于贪心算法，因为贪心算法是从局部最优来解决问题，而动态规划是全局最优的。

用动态规划的时候不可能在子问题还没有得到最优解的情况下就做出决策，而是必须等待子问题得到了最优解之后才对当下的情况做出决策，所以往往动态规划都可以用一个或多个递归式来描述。

而贪心算法却是先做出一个决策，然后在去解决子问题。

这就是贪心和动态规划的不同。

一般遇到一个动态规划类型的问题，都先要确定最优子结构，还有重叠子问题，这两个是动态规划最大的特征，然后就是要写动态规划的状态方程，这个步骤十分十分的重要的，写动归方程是需要一定的经验的，这可以通过训练来达到目的。

接着就是要自底向上的求解问题的，先将最小规模的子问题的最优解求出，一般都用一张表来记录下求得的解，到后来遇到同样的子问题的时候就可以直接查表得到答案，最后就是通过一步一步的迭代得出最后问题的答案了。

我的理解最重要的东西就是一定会要一个数组或者其他的存储结构存储得到的子问题的解。

这样就可以省很多时间，也就是典型的空间换时间动态规划的一种变形就是记忆化搜索，就是根据动归方程写出递归式，然后在函数的开头直接返回以前计算过的结果，当然这样做也需要一个存储结构记下前面计算过的结果，所以又成记忆化搜索下面是一个典型的记忆化搜索的题目，来自PKU 1579Function Run FunTime Limit:1000MS Memory Limit:10000KTotal Submit:2402 Accepted:1373DescriptionWe all love recursion! Don't we?Consider a three-parameter recursive function w(a, b, c):if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:1if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:w(20, 20, 20)if a < b and b < c, then w(a, b, c) returns:w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)otherwise it returns:w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15,b = 15,c = 15), the program takes hours to run because of the massive recursion.InputThe input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the abovetechnique, you are to calculate w(a, b, c) efficiently and print the result.OutputPrint the value for w(a,b,c) for each triple.Sample Input1 1 12 2 210 4 650 50 50-1 7 18-1 -1 -1Sample Outputw(1, 1, 1) = 2w(2, 2, 2) = 4w(10, 4, 6) = 523w(50, 50, 50) = 1048576w(-1, 7, 18) = 1这个题目如果直接用递归方程的话，肯定会超时(Time Limited Error),其实因为函数的递归会重复解决很多相当的子问题，一些子问题会被重复计算指数多次，所以为什么我们不要已经计算出的子问题的解记录下来呢，这就是记忆化搜索了，我们可以开一个数组用来记录已经解出的子问题，如果子问题的解在前面已经计算过，就直接返回，这就是本题要训练的要素。

动态规划问题动态规划(Dynamic Programming)是一种将复杂问题分解成更小的子问题并逐步解决的算法思想。

它通常用于解决涉及重叠子问题和最优子结构性质的问题，通过将问题分解成更小的子问题，并将解保存在一个表格中，以便后续的计算可以直接使用。

动态规划算法的核心思想是，通过维护一个辅助的状态表格来存储子问题的解，以便在需要用到子问题的解时，可以直接查表获取，避免重复计算。

在解决问题的过程中，我们通常会先从最小的子问题开始解决，并将解保存在表格中。

然后，根据较大规模子问题的解来逐步解决较小规模的子问题，最终得到整个问题的解。

动态规划算法的关键步骤可以描述如下：1. 定义子问题：将问题分解成更小规模的子问题，描述子问题的解与原问题解的关系；2. 定义状态：定义子问题的解与状态之间的对应关系，用于将子问题的解存储在状态表格中；3. 定义状态转移方程：描述较大规模子问题的解与较小规模子问题的解之间的关系，用于从表格中获取已计算的解；4. 初始化状态表格：将表格中所有的状态初始化为无效值，以便在获取解时可以判断是否已计算；5. 根据状态转移方程计算状态表格中的所有解；6. 根据问题的要求从状态表格中获取最优解。

动态规划算法可以用于解决各种问题，如最长递增子序列、最短路径、背包问题等。

通过分解问题、定义状态和状态转移方程，动态规划算法可以高效地求解复杂的问题，并避免重复计算。

在实际应用中，通过合理设计状态转移方程和思考问题的最优子结构性质，可以使动态规划算法更加高效和准确。

总之，动态规划是一种将问题分解成更小子问题的算法思想，通过保存子问题的解并使用状态转移方程，可以高效地求解复杂问题。

通过合理设计状态和思考最优子结构性质，可以使动态规划算法更加高效。

动态规划算法在实际应用中具有广泛的应用价值，在算法设计和问题求解过程中发挥着重要的作用。

动态规划算法详解和应用动态规划（Dynamic Programming）算法是从多个阶段中逐步逼近最优解的一种算法。

它的主要思想是将原问题拆分成若干个子问题，并使用已解决的子问题的解来推导还未解决的子问题。

在处理每个子问题时，都会保存之前已经部分解决过的子问题的结果。

借助这些结果来解决更复杂的问题。

动态规划算法因此得名。

本文将详细介绍动态规划算法的基本思想、步骤和应用。

动态规划算法的基本思想：当解决一个问题时，将其分解成若干个子问题并求解。

每个子问题的解只会记录一次，以避免重复求解。

因此，动态规划算法重复使用以前的子问题的解来解决当前的子问题。

在计算机编程中，动态规划通常需要做出一种递归解法，以解决问题的所有可能情况。

如果递归解法的效率太低，可以让它转化为带有动态规划思想的算法，其根据已经解决的子问题计算其它子问题。

动态规划算法的基本步骤：1. 定义状态: 状态是决定某个时刻或某个条件的变量（或变量集合）。

它反映了解决一个问题需要的参数信息。

例如，对于求解最长公共子序列问题来说，状态就是两个字符串的下标。

2. 定义转移：对于当前状态，转移就是从上一状态到达当前状态所要执行的操作（比如以左上角有没有两个字符为例，若匹配则加上当前结果，否则不加）3. 初始化状态：通常在定义状态时，会初始化状态。

在问题开始时，只需要初始化状态就可以得出问题的部分或全部答案。

4. 通常使用一维或多维数组存储状态。

状态也可以是其他容器，如哈希表、树和堆等。

5. 最后得到问题的最终答案。

动态规划算法的应用：1. 寻找最长/最短路径问题（例如：Dijkstra算法和Floyd算法）；2. 寻找最优二叉树（例如：Huffman编码算法）；3. 求解最大子数列问题（例如：Kadane算法）；4. 求解最长公共子序列问题（例如：LCS算法）；5. 求解最长回文子串（例如：Manacher算法）；6. 求解背包问题（例如：01背包、完全背包）。

记忆化搜索1．概念什么是记忆化搜索呢？搜索和动态规划各自的优缺点：搜索的低效在于没有能够很好地处理重叠子问题；动态规划虽然比较好地处理了重叠子问题，但是在有些拓扑关系比较复杂的题目面前，又显得无奈。

记忆化搜索正是在这样的情况下产生的，它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起，扬长避短，简单实用，在信息学中有着重要的作用。

用一个公式简单地说：记忆化搜索=搜索的形式+动态规划的思想。

既然它具有搜索的形式，那么我们也按照讨论搜索算法的方式讨论这个新事物：2．记忆化深度优先搜索（1）程序框架constnonsense=-1; {这个值可以随意定义，表示一个状态的最优值未知}var…… {全局变量定义}function work(s:statetype):longint;var…… {局部变量定义}beginif opt[s]<>nonsense thenbeginwork:=opt[s];exit;end; {如果状态s的最优值已经知道，直接返回这个值}枚举所有可以推出状态S的状态S1begintemp:=由S1推出的S的最优值 {有关work(s1)的函数} ;if (opt[s]=nonsense) or (temp优于opt[s])then opt[s]:=temp;end;work:=opt[s]; {用动态规划的思想推出状态s的最优值}end;记忆化深度优先搜索采用了一般的深度优先搜索的递归结构，但是在搜索到一个未知的状态时它总把它记录下来，为以后的搜索节省了大量的时间。

可见，记忆化搜索的实质是动态规划，效率也和动态规划接近；形式是搜索，简单易行，也不需要进行什么拓扑排序了。

（2）例子——words【问题描述】Io和Ao在玩一个单词游戏。

他们轮流说出一个仅包含元音字母的单词，并且后一个单词的第一个字母必须与前一个单词的最后一个字母一致。

游戏可以从任何一个单词开始。