《挑战程序设计竞赛》笔记
动态规划法的精妙之处
动态规划法（Dynamic Programming， DP）是一种在程序设计竞赛中广泛应用的算法设计方法。其核心思想是将复杂的问题分解为若干个子问题，通过记录子问题的解来避免重复计算，从而提高效率。就像古人所说的“前人栽树，后人乘凉”，动态规划法通过记忆化的方式，让我们能够站在巨人的肩膀上，轻松解决看似复杂的问题。
在《挑战程序设计竞赛》中，作者通过两个经典的问题——最长公共子序列（LCS）和矩阵链乘法（Matrix Chain Multiplication），生动地展示了动态规划法的魅力。这些问题不仅是程序设计竞赛中的常见题型，也是动态规划法的典型应用场景。
最长公共子序列问题
最长公共子序列问题是动态规划法的入门级经典问题。假设我们有两个字符串X和Y，要求找出它们的最长公共子序列。例如，给定X=”abcbdab”和Y=”bdcaba”，它们的最长公共子序列是”bdab”或”bcab”，长度为4。
动态规划法通过构建一个二维数组c[m+1][n+1]来解决这个问题，其中c[i][j]表示X的前i个字符和Y的前j个字符的最长公共子序列的长度。递推公式如下：
- 如果
X[i] == Y[j]，则c[i][j] = c[i-1][j-1] + 1。 - 否则，
c[i][j] = max(c[i-1][j]， c[i][j-1])。
通过填充这个二维数组，我们可以得到最长公共子序列的长度。这种方法的时间复杂度为O(mn)，空间复杂度为O(mn)。虽然看起来空间复杂度较高，但通过优化，可以将空间复杂度降低到O(n)。
矩阵链乘法问题
矩阵链乘法问题是动态规划法的进阶应用之一。假设我们有n个矩阵，尺寸分别为p0×p1， p1×p2 …， pn-1×pn，要求找到一种乘法顺序，使得总的乘法运算次数最少。
例如，给定矩阵链3×5， 5×15， 15×5， 5×10， 10×20， 20×25，最优的乘法顺序可以通过动态规划法找到。动态规划法通过构建一个二维数组dp[i][j]来记录矩阵链i到j的最小乘法次数，并记录每次合并时的成本。递推公式如下：
- 如果i == j，则
dp[i][j] = 0。 - 否则，
dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j])，其中k从i到j-1。
通过这种方法，我们可以高效地找到最优的乘法顺序，避免暴力枚举所有可能的顺序。
动态规划法的实战案例
最长公共子序列的实战案例
假设我们有以下输入：
3
abc
abc
abcbdab
bdcaba
输出结果为：
3
4
其中，第一组输入的最长公共子序列是”abc”，长度为3；第二组输入的最长公共子序列是”bdab”或”bcab”，长度为4。
矩阵链乘法的实战案例
假设我们有以下输入：
6
30 35
35 15
15 5
5 10
10 20
20 25
输出结果为15125。
通过动态规划法，我们可以快速找到最优的乘法顺序，并计算出最少的乘法次数。
动态规划法的总结与展望
动态规划法是一种非常强大的算法设计方法，尤其在处理具有最优子结构和重叠子问题的复杂问题时，展现出独特的优势。在《挑战程序设计竞赛》中，作者通过详细的讲解和丰富的案例，帮助读者深入理解动态规划法的核心思想和应用场景。
通过学习动态规划法，我们不仅能够提高程序设计竞赛中的解题速度和准确率，还能在面对实际问题时，找到更高效的解决方案。正如书中所说，动态规划法是一种“智慧的算法”，它教会我们如何在复杂的问题中找到简单的解决方案。
希望读者能够通过这本书，掌握动态规划法的精髓，并在未来的程序设计竞赛中大展身手！ 🚀