【算法训练-动态规划 零】动态规划解题框架

简介: 【算法训练-动态规划 零】动态规划解题框架

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说求最长递增子序列呀,最小编辑距离呀等等。

既然是要求最值,核心问题是什么呢?求解动态规划的核心问题是穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值呗。

动态规划基本概念

动态规划(Dynamic Programming,简称DP)算法是一种解决复杂问题的算法设计和优化技术,常用于解决具有重叠子问题性质和最优子结构性质的问题。它的核心思想是将一个大问题分解成一系列相互重叠的子问题,然后将子问题的解存储起来,以避免重复计算,从而节省时间

动态规划算法通常包括以下关键步骤:

  1. 定义子问题:将原问题分解成若干个子问题,并明确定义每个子问题的输入和输出。
  2. 构建状态转移方程:确定每个子问题与其他子问题之间的关系,即如何通过已解决的子问题来解决当前子问题。这通常通过递归或迭代方式建立状态转移方程。
  3. 初始化:初始化基本情况,通常是问题规模较小或无法再分时的边界情况。
  4. 自底向上求解或使用备忘录法:根据状态转移方程,从最小的子问题开始解决,逐步构建出更大规模的问题的解。可以使用自底向上的迭代方法或备忘录法来避免重复计算。
  5. 返回结果:根据状态转移方程求解出原问题的解。

动态规划广泛应用于各种领域,包括算法设计、优化问题、路径规划、序列比对、字符串处理、游戏策略等。经典的动态规划问题包括斐波那契数列、背包问题、最长公共子序列、最短路径问题

动态规划的优点是可以显著减少重复计算,提高效率,但其缺点是需要合理定义子问题和状态转移方程,有时需要额外的内存空间来存储中间结果。因此,在解决问题时,需要仔细分析问题的性质,确定是否适合使用动态规划算法。

问题类型:一个模型三个特征

什么样的问题适合用动态规划来解决呢?换句话说,动态规划能解决的问题有什么规律可循呢?这部分理论可以总结为“一个模型三个特征”。

一个模型

首先,我们来看,什么是“一个模型”?它指的是动态规划适合解决的问题的模型。我把这个模型定义为多阶段决策最优解模型,我们一般是用动态规划来解决最优问题。

解决问题的过程,需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列,经过这组决策序列,能够产生最终期望求解的最优值。

三个特征

什么是“三个特征”?它们分别是最优子结构、无后效性和重复子问题

1 最优子结构

最优子结构指的是,问题的最优解包含子问题的最优解。反过来说就是,我们可以通过子问题的最优解,推导出问题的最优解。如果我们把最优子结构,对应到我们前面定义的动态规划问题模型上,那我们也可以理解为,后面阶段的状态可以通过前面阶段的状态推导出来。最优子结构,就是目前的最优解可以由以前的最优解推导出来,也就是存在状态转移公式

2 无后效性

无后效性有两层含义,第一层含义是,在推导后面阶段的状态的时候,我们只关心前面阶段的状态值,不关心这个状态是怎么一步一步推导出来的。第二层含义是,某阶段状态一旦确定,就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型,其实基本上都会满足无后效性。无后效性 其实就是当前状态与路径无关、当前的决定不受后面的影响,子问题的最优决策只与子问题自己相关,与原始问题无关,解决子问题时候不用考虑原始问题,就和递归只要考虑当前层状态和处理一样

3 重复子问题

不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态

动态规划解题框架

虽然动态规划的核心思想就是穷举求最值,但是问题可以千变万化,穷举所有可行解其实并不是一件容易的事:

  1. 需要熟练掌握递归思维,只有列出正确的「状态转移方程」,才能正确地穷举。
  2. 需要判断算法问题是否具备「最优子结构」,是否能够通过子问题的最值得到原问题的最值。
  3. 动态规划问题存在「重叠子问题」,如果暴力穷举的话效率会很低,所以需要使用「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算

以上最难的是写出状态转移方程,给出一个思维框架

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义,按上面的套路走,最后的解法代码就会是如下的框架

# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result
# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            dp[状态1][状态2][...] = 求最值(选择1,选择2...)

示例:暴力递归

首先看一个斐波那契数列的暴力递归方法:

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

这个递归树怎么理解?就是说想要计算原问题 f(20),我就得先计算出子问题 f(19) 和 f(18),然后要计算 f(19),我就要先算出子问题 f(18) 和 f(17),以此类推。最后遇到 f(1) 或者 f(2) 的时候,结果已知,就能直接返回结果,递归树不再向下生长了

递归算法的时间复杂度怎么计算?就是用子问题个数乘以解决一个子问题需要的时间

首先计算子问题个数,即递归树中节点的总数。显然二叉树节点总数为指数级别,所以子问题个数为 O(2^n)。然后计算解决一个子问题的时间,在本算法中,没有循环,只有 f(n - 1) + f(n - 2) 一个加法操作,时间为 O(1)。

所以,这个算法的时间复杂度为二者相乘,即 O(2^n),指数级别,爆炸,观察递归树,很明显发现了算法低效的原因:存在大量重复计算,比如 f(18) 被计算了两次,而且你可以看到,以 f(18) 为根的这个递归树体量巨大,多算一遍,会耗费巨大的时间。更何况,还不止 f(18) 这一个节点被重复计算,所以这个算法及其低效。

这就是动态规划问题的第一个性质:重叠子问题

自顶向下:递归+备忘录

即然耗时的原因是重复计算,那么我们可以造一个「备忘录」,每次算出某个子问题的答案后别急着返回,先记到「备忘录」里再返回;每次遇到一个子问题先去「备忘录」里查一查,如果发现之前已经解决过这个问题了,直接把答案拿出来用,不要再耗时去计算了

一般使用一个数组充当这个「备忘录」,当然你也可以使用哈希表(字典),思想都是一样的

int fib(int N) {
    // 备忘录全初始化为 0
    int[] memo = new int[N + 1];
    // 进行带备忘录的递归
    return dp(memo, N);
}
// 带着备忘录进行递归
int dp(int[] memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过,不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
}

实际上,带「备忘录」的递归算法,把一棵存在巨量冗余的递归树通过「剪枝」,改造成了一幅不存在冗余的递归图,极大减少了子问题(即递归图中节点)的个数

子问题个数,即图中节点的总数,由于本算法不存在冗余计算,子问题就是 f(1), f(2), f(3) … f(20),数量和输入规模 n = 20 成正比,所以子问题个数为 O(n)。解决一个子问题的时间,同上,没有什么循环,时间为 O(1),所以,本算法的时间复杂度是 O(n),比起暴力算法,是降维打击

自底向上:状态转移表法(DP Table)

带备忘录的递归和常见的动态规划解法已经差不多了,只不过这种解法是「自顶向下」进行「递归」求解,我们更常见的动态规划代码是「自底向上」进行「递推」求解

注意我们刚才画的递归树(或者说图),是从上向下延伸,都是从一个规模较大的原问题比如说 f(20),向下逐渐分解规模,直到 f(1) 和 f(2) 这两个 base case,然后逐层返回答案,这就叫「自顶向下」。

啥叫「自底向上」?反过来,我们直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)(base case)开始往上推,直到推到我们想要的答案 f(20)。这就是「递推」的思路这也是动态规划一般都脱离了递归,而是由循环迭代完成计算的原因

有了上一步「备忘录」的启发,我们可以把这个「备忘录」独立出来成为一张表,通常叫做 DP table,在这张表上完成「自底向上」的推算

int fib(int N) {
    if (N == 0) return 0;
    int[] dp = new int[N + 1];
    // base case
    dp[0] = 0; dp[1] = 1;
    // 状态转移
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[N];
}

实际上,带备忘录的递归解法中的那个「备忘录」memo 数组,最终完成后就是这个解法中的 dp 数组

什么是状态转移方程?把参数 n 想做一个状态,这个状态 n 是由状态 n - 1 和状态 n - 2 转移(相加)而来,这就叫状态转移,仅此而已。 你会发现,上面的几种解法中的所有操作,例如 return f(n - 1) + f(n - 2),dp[i] = dp[i - 1] + dp[i - 2],以及对备忘录或 DP table 的初始化操作,都是围绕这个方程式的不同表现形式

根据斐波那契数列的状态转移方程,当前状态 n 只和之前的 n-1, n-2 两个状态有关,其实并不需要那么长的一个 DP table 来存储所有的状态,只要想办法存储之前的两个状态就行了

int fib(int n) {
    if (n == 0 || n == 1) {
        // base case
        return n;
    }
    // 分别代表 dp[i - 1] 和 dp[i - 2]
    int dp_i_1 = 1, dp_i_2 = 0;
    for (int i = 2; i <= n; i++) {
        // dp[i] = dp[i - 1] + dp[i - 2];
        int dp_i = dp_i_1 + dp_i_2;
        // 滚动更新
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i_1;
}

所以,可以进一步优化,把空间复杂度降为 O(1)

动态规划解题基本步骤及应用领域

动态规划(Dynamic Programming,简称DP)是一种解决复杂问题的算法设计技术,常用于优化问题和组合问题的求解。它通过将原问题分解成子问题,并保存子问题的解,以避免重复计算,从而提高算法的效率。动态规划通常用于解决具有重叠子问题和最优子结构性质的问题。

动态规划的基本思想可以总结为以下几个步骤:

  1. 定义问题的状态:首先要明确定义问题的状态,这些状态可以用来描述问题的各种情况。
  2. 找到状态转移方程:状态转移方程描述了问题之间的联系,即如何从一个状态转移到另一个状态。这通常涉及到问题的递归关系,通过这个关系可以从较小规模的子问题得到更大规模的问题的解。
  3. 初始化状态:确定初始状态的值,这通常是问题规模最小的情况下的解。
  4. 自底向上或自顶向下求解:动态规划可以采用自底向上(Bottom-Up)或自顶向下(Top-Down)的方式求解问题。自底向上是从最小的状态开始逐步计算,直到得到最终问题的解;自顶向下是从最终问题开始,递归地计算子问题的解,直到达到最小状态。
  5. 根据问题的要求,从状态中找到最终解

动态规划常见的应用领域包括:

  1. 最长公共子序列问题:在两个序列中找到一个最长的共同子序列,用于比较字符串相似性。
  2. 背包问题:在给定一定容量的背包和一组物品的情况下,选择一些物品放入背包,使得物品的总价值最大或总重量不超过背包容量。
  3. 最短路径问题:求解图中两点之间的最短路径,如Dijkstra算法和Floyd-Warshall算法。
  4. 硬币找零问题:给定一组硬币面额和一个目标金额,找到使用最少数量的硬币组合成目标金额。
  5. 斐波那契数列问题:求解斐波那契数列的第n个数,通过动态规划可以避免重复计算。

动态规划是一种强大的问题求解方法,但它并不适用于所有类型的问题。在使用动态规划时,需要仔细分析问题的性质,确保问题具有重叠子问题和最优子结构性质,以确保动态规划算法能够有效地解决问题。

贪心算法、动态规划、回溯算法

这三个算法解决问题的模型,都可以抽象成多阶段决策最优解模型

  • 回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题,我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况,然后对比得到最优解。不过,回溯算法的时间复杂度非常高,是指数级别的,只能用来解决小规模数据的问题。对于大规模数据的问题,用回溯算法解决的执行效率就很低了。解决最多的问题,性能最差
  • 尽管动态规划比回溯算法高效,但是,并不是所有问题,都可以用动态规划来解决。能用动态规划解决的问题,需要满足三个特征,最优子结构、无后效性和重复子问题。在重复子问题这一点上,动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题,不能有重复子问题,而动态规划正好相反,动态规划之所以高效,就是因为回溯算法实现中存在大量的重复子问题。解决较多的问题,性能较好
  • 贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效,代码实现也更加简洁。不过,它可以解决的问题也更加有限。它能解决的问题需要满足三个条件,最优子结构、无后效性和贪心选择性(这里我们不怎么强调重复子问题)。其中,最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是,通过局部最优的选择,能产生全局的最优选择。每一个阶段,我们都选择当前看起来最优的决策,所有阶段的决策完成之后,最终由这些局部最优解构成全局最优解,解决最少的问题,性能最好

动态规划、递归、分治的区别

下面是动态规划、递归和分治这三种算法的相同点和不同点的表格展示:

特点 动态规划 递归 分治
求解方式 自底向上 自顶向下 分而治之
重复计算处理 避免重复计算,通过存储子问题的解来提高效率 可能重复计算相同的子问题 分解问题并独立处理子问题
时间复杂度 通常具有较低的时间复杂度 可能具有较高的时间复杂度 通常具有中等的时间复杂度
适用性 适用于具有重叠子问题性质和最优子结构性质的问题 适用于结构天然呈递归性质的问题 适用于问题可以分解为独立的子问题
经典问题举例 背包问题、最短路径问题、斐波那契数列 树形结构的问题、图遍历 快速排序、归并排序
记忆化/缓存 通过存储中间结果,具有记忆化的特点 可以使用记忆化技巧来减少重复计算 分治通常不涉及记忆化
稳定性 具有稳定性,不受输入数据顺序影响 可能受输入数据顺序影响 通常具有稳定性,不受输入数据顺序影响

这个表格概括了动态规划、递归和分治算法之间的一些主要相同点和不同点。需要注意的是,这些算法的选择取决于具体问题的性质和要求,有时候也可以根据问题的特点将它们结合使用,以获得更好的性能和效果。

动态规划、递归、分治处理的题目分类

适用于这些算法思想的题目

动态规划处理的高频算法题

动态规划是一个非常强大的算法技巧,适用于解决各种高频的算法问题。以下是一些使用动态规划解决的常见高频算法题目:

  1. 斐波那契数列问题:计算斐波那契数列的第n个数,可以使用动态规划来避免指数级的重复计算。
  2. 背包问题:如 0-1 背包问题、完全背包问题、多重背包问题等,动态规划可用于优化资源分配问题。
  3. 最长公共子序列问题:寻找两个字符串的最长公共子序列,动态规划可用于解决字符串匹配和相似性比较问题。
  4. 最长递增子序列问题:寻找一个数组中最长的递增子序列,常用于优化问题和排序问题。
  5. 最短路径问题:如 Dijkstra 算法、Floyd-Warshall 算法,用于在图中找到最短路径或最短距离。

6. 编辑距离问题:计算两个字符串之间的最小编辑操作数,如插入、删除和替换操作。

7. 股票买卖问题:寻找股票价格数组中的最佳买卖时机,以获得最大的利润。

  1. 子集和问题:确定给定集合中是否存在一个子集,其元素之和等于特定目标值。
  2. 矩阵链乘法问题:在给定一组矩阵的情况下,确定它们相乘的最佳顺序以最小化乘法运算的次数。
  3. 字符串匹配问题:如正则表达式匹配、通配符匹配等,用于模式匹配和文本搜索。

这些问题只是动态规划可以解决的众多示例之一。动态规划的思想可以应用于各种优化和最优化问题,它的关键是将问题分解成子问题并找到适当的状态转移规则。因此,当你面对一个复杂的问题时,考虑是否可以使用动态规划来提高问题求解的效率和准确性。

分治算法处理的高频算法题

分治算法是一种重要的算法技巧,适用于解决各种高频的算法问题,特别是分而治之的思想。以下是一些使用分治算法解决的常见高频算法题目:

  1. 归并排序:分治算法的经典示例之一,用于将一个大数组分割成较小的子数组,排序子数组,然后将它们合并以得到有序数组。
  2. 快速排序:另一种基于分治思想的排序算法,通过选择一个基准元素,将数组划分成两个子数组,然后递归地对子数组进行排序。
  3. 连续子数组的最大和:给定一个整数数组,查找具有最大和的连续子数组。分治算法可以用于高效解决这个问题。
  4. 求解最近点对问题:给定一个包含多个点的平面,找到最接近的一对点。该问题可以通过分治算法以较低的时间复杂度解决。
  5. 矩阵乘法:分治算法可以用于将矩阵分割成子矩阵,然后递归地进行矩阵乘法操作,以减少计算次数。
  6. 大整数乘法:用于计算两个大整数的乘积,分治算法可以用于将大整数分解为较小的整数,并递归地计算它们的乘积。
  7. 众数问题:查找数组中出现次数超过一半的元素,分治算法可以在线性时间内解决这个问题。
  8. 合并K个有序链表:将K个有序链表合并为一个有序链表,分治算法可以用于高效解决这个问题。
  9. 寻找第K大/小的元素:在一个未排序的数组中找到第K大或第K小的元素,分治算法可以用于解决这个问题。
  10. 求解凸多边形的最小包围矩形:给定一个凸多边形,找到包围它的最小矩形。分治算法可用于高效计算最小包围矩形。

这些问题只是分治算法可以解决的众多示例之一。分治算法的关键思想是将问题分解为相互独立的子问题,然后将子问题的解合并以得到原问题的解。当你面对一个需要分而治之的问题时,考虑是否可以使用分治算法来提高问题求解的效率和准确性。

递归算法处理的高频算法题

递归算法是一种常见且强大的算法技巧,适用于解决各种高频的算法问题。以下是一些使用递归算法解决的常见高频算法题目:

  1. 二叉树遍历:包括前序遍历、中序遍历、后序遍历等,用于访问和处理二叉树的节点。
  2. 分解问题:许多问题可以通过将它们分解为更小的相似子问题来解决,例如斐波那契数列、汉诺塔问题等。
  3. 递归的数据结构:如链表、树、图等数据结构的处理通常使用递归来实现。
  4. 组合和排列问题:生成所有可能的组合或排列,如子集生成、排列生成等。
  5. 回溯算法:解决一些组合优化问题,如八皇后问题、数独问题等。
  6. 图的遍历:深度优先搜索(DFS)和广度优先搜索(BFS)是递归的常见应用,用于解决图相关的问题。
  7. 递归的搜索和查找:二分查找、树的搜索、图的最短路径等问题可以使用递归算法解决。
  8. 分治算法:分治算法的核心思想就是递归,如归并排序、快速排序等。
  9. 递归背包问题:解决背包问题的变种,如动态规划中的背包问题。
  10. 字符串处理:字符串匹配、编辑距离、正则表达式匹配等问题通常可以使用递归来解决。

这些问题只是递归算法可以解决的众多示例之一。递归算法的关键思想是将问题分解为更小的相似问题,并通过递归调用自身来解决这些子问题。当你面对一个需要不断分解问题的情况时,考虑是否可以使用递归来解决,但需要小心避免无限递归,确保有适当的终止条件。

相关文章
|
1月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
25天前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
55 2
动态规划算法学习三:0-1背包问题
|
27天前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
50 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
7天前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
1月前
|
机器学习/深度学习 算法 决策智能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
|
25天前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
58 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
25天前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
103 0
动态规划算法学习二:最长公共子序列
|
11天前
|
算法
”回溯算法“框架及练习题
”回溯算法“框架及练习题
23 0
|
22天前
|
算法 Java 程序员
【算法每日一练及解题思路】有n级台阶,一次只能上1级或2级,共有多少种走法?
本文深入解析了“爬楼梯问题”,探讨了递归与迭代两种解法,并提供了Java代码实现。通过分析问题本质,帮助读者理解动态规划技巧,提高解决实际编程问题的能力。关键词:Java, 算法, 动态规划, 爬楼梯问题, 递归, 迭代。
45 0
|
25天前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
90 0