动态规划与贪心算法：原理、应用与复杂度分析

# 动态规划与贪心算法：原理、应用与复杂度分析 ## 1. 动态规划基础 ### 1.1 动态规划问题引入 在动态规划中，我们经常会遇到计算最小成本路径等问题。例如，在顶点集合 $\{1, 2, 3, 4, \cdots, n\}$ 中，将顶点 1 作为起点和终点，对于其他每个顶点 $i$（除 1 外），要找到从 1 出发，以 $i$ 为终点且所有顶点仅出现一次的最小成本路径。我们定义 $C(S, i)$ 为从 1 出发，访问集合 $S$ 中每个顶点恰好一次并以 $i$ 为终点的最小成本路径的成本。 - 当 $S$ 的大小为 2 时，$S$ 必定为 $\{1, i\}$，此时 $C(S, i) = dist(1, i)$。 - 当 $S$ 的大小大于 2 时，$C(S, i) = \min \{C(S - i, j) + dis(j, i)\}$，其中 $j$ 属于 $S$，且 $j \neq i$ 且 $j \neq 1$。 ### 1.2 经典问题求解 #### 1.2.1 斐波那契数列 - **分治法**： ```c int fibo(int n) { if (n == 0) return n; else if (n == 1) return n; else return fibo(n - 1) + fibo(n - 2); } ``` 时间复杂度为 $O(2^{n/2})$。 - **动态规划法**： ```c int fibo (int n) { int arr[n]; arr[0] = 0; arr[1] = 1; if (n == 0) return n; else if (n == 1) return n; else { for (int i = 2; i <= n; i++) arr[i] = arr[i - 1] + arr[i - 2]; return arr[n]; } } ``` 时间复杂度为 $O(n)$。 #### 1.2.2 卡特兰数 - **递归法**： ```c if (n <= 1) return 1; res = 0; for (int i = 0; i < n; i++) res += catalan(i) * catalan(n - i - 1); return res; ``` 时间复杂度为 $O(3^n)$。 - **动态规划法**： ```c catalan[0] = catalan[1] = 1; for (int i = 2; i <= n; i++) { catalan[i] = 0; for (int j = 0; j < i; j++) catalan[i] += catalan[j] * catalan[i - j - 1]; } return catalan[n]; ``` 时间复杂度为 $O(n^2)$。 #### 1.2.3 欧拉数 ```c int eulerian(int n, int m) { if (m >= n || n == 0) return 0; if (m == 0) return 1; return (n - m) * eulerian(n - 1, m - 1) + (m + 1) * eulerian(n - 1, m); } ``` #### 1.2.4 雅可比斯特哈数 ```c f[0..n] = -1; f[1] = 1; f[0] = 0; Jacobsthal(n, f): if f[n][k] != -1 return f[n][k]; return Jacobsthal(n - 1, f) + 2 * Jacobsthal(n - 2, f); ``` ### 1.3 矩阵运算与路径问题 #### 1.3.1 矩阵更新 通过一系列矩阵更新操作来计算最短路径等问题。例如，给定矩阵 $D_0$，通过不断更新得到 $D_1, D_2, D_3, D_4$ 等。 - $D_0 = \begin{bmatrix} 0 & 4 \\ \infty & 0 \\ 1 & 3 \\ 1 & 5 \\ \infty & \infty \\ \infty & \infty \\ 0 & 3 \\ \infty & 0 \end{bmatrix}$ - 通过公式 $D_{k}[i][j] = \min (D_{k - 1}[i][j], D_{k - 1}[i][k] + D_{k - 1}[k][j])$ 进行更新。 #### 1.3.2 路径数量计算 为了找到不同长度的路径，需要对矩阵进行顺序相乘。例如，给定矩阵 $D$： ```plaintext D = ⎡ ⎢⎢⎢⎢⎣ 0 1 1 0 0 0 0 0 1 1 0 1 0 0 0 2 0 1 0 0 0 0 0 1 0 ⎤ ⎥⎥⎥⎥⎦ ``` 计算 $D^2 = D * D$，$D^3$，$D^4$ 等，然后可以计算不同长度路径的数量。 - 偶数路径数量：$D_2 + D_4$ - 奇数路径数量：$D_1 + D_3$ ### 1.4 矩阵链乘法 矩阵链乘法的目标是找到一种最优的矩阵相乘顺序，以最小化标量乘法的次数。设 $M_{ij}$ 为矩阵链 $A_iA_{i + 1}\cdots A_j$ 的最小乘法次数。 - 当 $i = j$ 时，$M_{ij} = 0$。 - 当 $i < j$ 时，$M_{ij} = \min_{i \leq k \leq j - 1} (M_{ik} + M_{k + 1j} + d_{i - 1}d_kd_j)$。 例如，给定 $d_0 = 10$，$d_1 = 20$，$d_2 = 50$，$d_3 = 1$，$d_4 = 100$，计算得到： | | 1 | 2 | 3 | 4 | | --- | --- | --- | --- | --- | | 1 | 0 | 10000 | 300 | 1300 | | 2 | 0 | 1000 | 3000 | | | 3 | 0 | 5000 | | | | 4 | 0 | | | | ## 2. 贪心算法基础 ### 2.1 贪心算法原理 贪心算法是一种用于优化问题的简单算法。它在每一步都做出当前看起来最优的选择，希望通过这种方式找到解决整个问题的最优方法。需要注意的是： - 贪心算法在解决问题的每个阶段，不考虑之前或之后的选择，只选择看起来最好的元素。 - 这些算法不能保证得到最优答案，因为它们在选择答案时不考虑前一步或下一步的情况。 贪心算法是一个迭代过程，每次迭代包含三个步骤： 1. **选择**：选择要添加到集合中的元素。这是一个贪心选择，即不考虑之前或之后的选择，在该阶段选择看起来最好的元素。 2. **可行性检查**：在贪心选择一个元素后，算法需要考虑是否可以将其添加到之前的答案集合中。有时添加一个元素会违反问题的基本条件之一，必须加以考虑。如果添加这个元素不违反任何条件，则将其添加；否则将其排除，并根据第一步选择另一个元素添加。如果没有其