动态规划练习题详解

# 动态规划练习题详解 ## 1. 预备知识 ### 1.1 动态规划的适用性分析 - **无重叠子问题时动态规划无用**：动态规划的核心在于通过解决重叠子问题来提高效率。如果一个问题不存在公共（重叠）子问题，那么动态规划的优势就无法体现，因为没有重复计算的部分，也就无需存储中间结果以避免重复计算。 - **动态规划对数组二分查找无用**：二分查找每次将搜索范围缩小一半，每次操作都是独立的，不存在重叠子问题。它通过不断比较中间元素与目标值的大小，逐步缩小搜索区间，因此动态规划无法在这个过程中发挥作用。 - **动态规划对计算第 n 个斐波那契数有用**：斐波那契数列的定义为 \(F_n = F_{n - 1} + F_{n - 2}\)，其中 \(F_0 = 0\)，\(F_1 = 1\)。在计算 \(F_n\) 时，会多次重复计算 \(F_{n - 1}\)、\(F_{n - 2}\) 等子问题，动态规划可以通过存储这些子问题的结果，避免重复计算，从而提高效率。 ### 1.2 不同解法的区别 递归、记忆化（自顶向下）和制表（自底向上）是解决问题的三种不同方法，它们的区别如下： | 解法 | 描述 | 特点 | | ---- | ---- | ---- | | 递归 | 直接根据问题的递归定义编写函数，通过不断调用自身来解决子问题。 | 代码简洁，但可能存在大量重复计算，效率较低。 | | 记忆化（自顶向下） | 在递归的基础上，使用一个数组或哈希表来存储已经计算过的子问题的结果，避免重复计算。 | 结合了递归的简洁性和动态规划的效率，适用于问题的递归结构明显的情况。 | | 制表（自底向上） | 从最小的子问题开始，逐步计算出更大的子问题的结果，直到得到最终结果。 | 通常使用迭代的方式实现，效率较高，但代码可能相对复杂。 | ### 1.3 最优子结构性质与动态规划 如果一个问题的最优解可以通过其子问题的最优解得到，那么这个问题就具有最优子结构性质。动态规划适用于具有最优子结构性质的问题，因为它可以通过解决子问题的最优解，逐步构建出原问题的最优解。 ### 1.4 图中路径问题的最优性原理验证 - **所有节点对之间的最短路径**：在图中寻找所有节点对之间的最短路径时，最优性原理成立。因为如果从节点 \(u\) 到节点 \(v\) 的最短路径经过节点 \(w\)，那么从 \(u\) 到 \(w\) 的子路径和从 \(w\) 到 \(v\) 的子路径也一定是最短路径。 - **所有节点对之间的最长路径**：在图中寻找所有节点对之间的最长路径时，最优性原理不成立。因为最长路径问题不具有最优子结构性质，即最长路径的子路径不一定是最长路径。 ## 2. 数学数字问题 ### 2.1 斐波那契数 #### 2.1.1 分治法 分治法通过递归地计算 \(F_{n - 1}\) 和 \(F_{n - 2}\) 来得到 \(F_n\)，代码如下： ```python def fibonacci_divide_and_conquer(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci_divide_and_conquer(n - 1) + fibonacci_divide_and_conquer(n - 2) ``` #### 2.1.2 动态规划法 动态规划法通过制表的方式，从 \(F_0\) 和 \(F_1\) 开始，逐步计算出 \(F_n\)，代码如下： ```python def fibonacci_dynamic_programming(n): if n == 0: return 0 elif n == 1: return 1 dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] ``` #### 2.1.3 运行时间分析 分治法的时间复杂度为 \(O(2^n)\)，因为每次递归都会产生两个子问题，会导致大量的重复计算。动态规划法的时间复杂度为 \(O(n)\)，因为只需要遍历一次数组。 ### 2.2 卡特兰数 卡特兰数在许多有趣的计数问题中出现，如括号匹配、二叉搜索树的数量等。 #### 2.2.1 分治法 分治法通过递归地计算子问题来得到第 n 个卡特兰数，代码如下： ```python def catalan_divide_and_conquer(n): if n <= 1: return 1 result = 0 for i in range(n): result += catalan_divide_and_conquer(i) * catalan_divide_and_conquer(n - i - 1) return result ``` #### 2.2.2 动态规划法 动态规划法通过制表的方式，从 \(C_0\) 和 \(C_1\) 开始，逐步计算出 \(C_n\)，代码如下： ```python def catalan_dynamic_programming(n): if n <= 1: return 1 dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 for i in range(2, n + 1): for j in range(i): dp[i] += dp[j] * dp[i - j - 1] return dp[i] ``` #### 2.2.3 使用二项式系数计算 第 n 个卡特兰数可以通过二项式系数计算：\(C_n = \frac{1}{n + 1} \binom{2n}{n}\)，代码如下： ```python from math import factorial def catalan_binomial_coefficient(n): return factorial(2 * n) // (factorial(n + 1) * factorial(n)) ``` #### 2.2.4 运行时间分析 分治法的时间复杂度为 \(O(2^n)\)，动态规划法的时间复杂度为 \(O(n^2)\)，使用二项式系数计算的时间复杂度为 \(O(n)\)。 ### 2.3 其他数字问题 - **贝尔数**：贝尔数表示将一个集合进行划分的方式数，可以使用动态规划来解决。 - **二项式系数 \(C(n, k)\)**：可以使用动态规划算法来计算二项式系数 \(C(n, k)\)。 - **排列系数 \(P(n, k)\)**：可以使用动态规划算法来计算排列系数 \(P(n, k)\)。 - **其他数字**：如 Lobb 数、欧拉数、Delannoy 数、Entringer 数、Rencontres 数、Jacobsthal 数和 Jacobsthal - Lucas 数、超级丑数等，都可以使用动态规划来设计算法。 ## 3. 所有节点对之间的最短路径问题 ### 3.1 Floyd - Warshall 算法 Floyd - Warshall 算法用于解决所有节点对之间的最短路径问题，其基本思想是通过不断更新节点对之间的最短路径长度，最终得到所有节点对之间的最短路径。算法的伪代码如下： ```plaintext Function Floyd - Warshall(C, n) for i := 1 to n do for j := 1 to n do if (i, j) ∈ E then D[i, j] := cost of edge (i, j) else D[i, j] := ∞ D[i, i] := 0 for k := 1 to n do for i := 1 to n do for j := 1 to n do if D[i, k] + D[k, j] < D[i, j] then D[i, j] := D[i, k] + D[k, j] re ```