目录

一、动态规划算法基础

1.1 动态规划是什么

1.2 动态规划适用场景

1.3 动态规划解题步骤

二、典型实例 1：0 - 1 背包问题

2.1 问题描述

2.2 状态定义与转移方程

2.3 Python 代码实现

2.4 代码分析与优化

三、典型实例 2：最长公共子序列（LCS）

3.1 问题描述

3.2 状态定义与转移方程

3.3 Python 代码实现

3.4 代码分析与应用场景

四、典型实例 3：最长回文子串

4.1 问题描述

4.2 状态定义与转移方程

4.3 Python 代码实现

4.4 代码分析与优化思路

五、总结与拓展

5.1 动态规划算法总结

5.2 拓展学习建议

---

一、动态规划算法基础

1.1 动态规划是什么

动态规划（Dynamic Programming，DP）是一种通过把原问题分解为相对简单的子问题的方式来解决复杂问题的方法。它的基本思想是将待求解问题分解成不同部分（即子问题），然后依据子问题的解以得出原问题的解 ，而子问题又可递归地分解为子子问题。通常许多子问题可能会重复出现 (重复子问题)，DP 试图仅仅解每个子问题一次，在求得每个子问题的解后将其保存起来，下次再需要求解相同子问题时，直接查表得到，从而减少计算量，它的精髓在于记住求过的解来节省时间，体现了以空间换时间的算法思想。

举个简单的例子，在计算斐波那契数列时，常规的递归方法会有大量的重复计算，比如计算 F (n) 时，F (n - 1) 和 F (n - 2) 可能会被重复计算多次。而动态规划会将已经计算过的 F (n) 保存起来，当再次需要计算 F (n) 时，直接从保存的结果中获取，避免了重复计算，大大提高了计算效率。

1.2 动态规划适用场景

适合用动态规划解决的问题通常具有以下特点：

• 最优子结构：问题的最优解可以通过子问题的最优解递归构建。例如在背包问题中，背包总容量为 W，物品集合为 n 个。我们可以将这个问题划分为两个子问题：是否选择某个物品 i。如果选择该物品，问题就转化为容量为 W - wi 的最优解；如果不选择，问题则变为容量为 W 时剩下 n - 1 个物品的最优解。两个子问题的最优解决定了整体问题的最优解。

• 重叠子问题：在递归求解的过程中，不同的阶段可能会遇到相同的子问题。比如在斐波那契数列求解问题中，计算 F (n) 时需要计算 F (n - 1) 和 F (n - 2)，但是在计算 F (n - 1) 时又会再次计算 F (n - 2) ，这就是重叠子问题。如果不进行保存，计算过程中会出现大量的重复计算。

• 无后效性：某阶段的状态一旦确定，就不受这个状态以后决策的影响。这意味着某个状态所涉及的决策只依赖于当前的状态和前面的决策，而不会受到将来决策的影响。例如在路径规划问题中，选择到达某一个点 A 的最短路径不需要考虑之前是通过哪条路径到达的，只需要知道从点 A 到终点的距离以及经过 A 的最短路径即可。因此，当前阶段的决策只取决于当前状态，而不会依赖之前如何走到这个状态。

1.3 动态规划解题步骤

动态规划解题一般有以下步骤：

• 定义状态：确定问题的状态表示，通常用数组或变量来记录状态。例如在背包问题中，可以用 dp [i][j] 表示考虑前 i 个物品，背包容量为 j 时的最大价值。

• 确定状态转移方程：找出不同状态之间的递推关系。比如在背包问题中，对于第 i 个物品，有放入背包和不放入背包两种情况，状态转移方程为 dp [i][j] = max (dp [i - 1][j], dp [i - 1][j - w [i]] + v [i])，其中 w [i] 是第 i 个物品的重量，v [i] 是第 i 个物品的价值。

• 初始化：设置初始状态的值，比如 dp [0][0] = 0，表示没有物品且背包容量为 0 时的价值为 0 。

• 计算结果：根据状态转移方程和初始化条件，逐步计算出最终所需的结果。一般是通过循环来实现状态的转移和计算。

二、典型实例 1：0 - 1 背包问题

2.1 问题描述

0 - 1 背包问题是一个经典的组合优化问题。假设有一个背包，它的容量为W，现在有n个物品，每个物品都有对应的重量w[i]和价值v[i]，并且每个物品只有一个（即只能选择放入背包或者不放入背包，这就是 “0 - 1” 的含义，0 表示不放入，1 表示放入）。我们的目标是在不超过背包容量的前提下，选择一些物品放入背包，使得背包中物品的总价值最大 。

例如，背包容量W = 5，有 3 个物品，重量分别为[2, 3, 1]，价值分别为[3, 4, 2]。我们需要从这 3 个物品中选择，使得放入背包的物品总重量不超过 5，并且总价值最大。

2.2 状态定义与转移方程

• 状态定义：定义dp[i][j]表示考虑前i个物品，背包容量为j时的最大价值。

• 状态转移方程推导：

• • 对于第i个物品，有两种情况：

• • • 不放入第i个物品：此时背包的价值就是考虑前i - 1个物品，背包容量仍为j时的价值，即dp[i][j] = dp[i - 1][j]。

• • • 放入第i个物品：前提是背包容量j要大于等于第i个物品的重量w[i] ，此时背包的价值为考虑前i - 1个物品，背包容量为j - w[i]时的价值加上第i个物品的价值v[i]，即dp[i][j] = dp[i - 1][j - w[i]] + v[i]。

• • 综合以上两种情况，状态转移方程为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) （当j >= w[i]时）；当j < w[i]时，因为放不下第i个物品，所以dp[i][j] = dp[i - 1][j]。

2.3 Python 代码实现

def knapsack_01(weights, values, capacity):

n = len(weights)

# 创建二维数组dp并初始化边界条件

dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):

for j in range(1, capacity + 1):

if weights[i - 1] <= j:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])

else:

dp[i][j] = dp[i - 1][j]

return dp[n][capacity]

# 示例数据

weights = [2, 3, 1]

values = [3, 4, 2]

capacity = 5

print(knapsack_01(weights, values, capacity))

代码解释：

• weights列表存储每个物品的重量，values列表存储每个物品的价值，capacity表示背包的容量。

• dp是一个二维列表，dp[i][j]表示考虑前i个物品，背包容量为j时的最大价值，初始化dp数组，所有元素初始化为 0 。

• 外层循环遍历物品，内层循环遍历背包容量。

• 如果当前物品的重量小于等于当前背包容量，就根据状态转移方程更新dp[i][j]；否则，直接继承上一个状态的值。

• 最后返回dp[n][capacity]，即考虑所有物品，背包容量为capacity时的最大价值。

2.4 代码分析与优化

• 时间复杂度：代码中有两层嵌套循环，外层循环遍历物品数量n次，内层循环遍历背包容量capacity次，所以时间复杂度为\(O(n \times capacity)\) 。

• 空间复杂度：使用了一个二维数组dp，大小为\((n + 1) \times (capacity + 1)\)，所以空间复杂度为\(O(n \times capacity)\) 。

优化方向：

• 空间优化：观察状态转移方程可以发现，dp[i][j]只与dp[i - 1][j]和dp[i - 1][j - w[i]]有关，即只与上一层的状态有关，因此可以使用滚动数组将二维数组优化为一维数组，从而将空间复杂度降低到\(O(capacity)\)。优化后的代码如下：

def knapsack_01_optimized(weights, values, capacity):

n = len(weights)

dp = [0 for _ in range(capacity + 1)]

for i in range(n):

for j in range(capacity, weights[i] - 1, -1):

dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

return dp[capacity]

# 示例数据

weights = [2, 3, 1]

values = [3, 4, 2]

capacity = 5

print(knapsack_01_optimized(weights, values, capacity))

内层循环从大到小遍历，是为了保证每个物品只被考虑一次，如果从小到大遍历，会导致同一个物品被多次放入背包 。

三、典型实例 2：最长公共子序列（LCS）

3.1 问题描述

最长公共子序列（Longest Common Subsequence，LCS）问题是指在两个序列中，找出它们共同拥有的最长子序列。子序列是指从原序列中删除一些元素（也可以不删除）后得到的新序列，不要求元素在原序列中连续。例如，对于序列X = [1, 3, 4, 5, 6, 7, 7, 8]和序列Y = [3, 5, 7, 4, 8, 6, 7, 8, 2]，它们的最长公共子序列是[3, 5, 7, 8]，长度为 4 。

3.2 状态定义与转移方程

• 状态定义：定义dp[i][j]表示序列X的前i个元素和序列Y的前j个元素的最长公共子序列的长度。

• 状态转移方程推导：

• • 当X[i - 1] == Y[j - 1]时，说明当前元素是公共子序列的一部分，那么dp[i][j] = dp[i - 1][j - 1] + 1 。例如，序列X = [a, b, c]，序列Y = [a, b, d]，当考虑到第三个元素时，X[2] == Y[2]，此时最长公共子序列长度就是前两个元素的最长公共子序列长度加 1 。

• • 当X[i - 1] != Y[j - 1]时，说明当前元素不是公共子序列的一部分，那么dp[i][j]取dp[i - 1][j]和dp[i][j - 1]中的较大值。比如序列X = [a, b, c]，序列Y = [a, d, e]，当考虑到第三个元素时，X[2] != Y[2]，此时dp[3][3]就要在dp[2][3]和dp[3][2]中选择较大值。

状态转移方程为：\( dp[i][j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ dp[i - 1][j - 1] + 1 & \text{if } X[i - 1] = Y[j - 1] \\ \max(dp[i - 1][j], dp[i][j - 1]) & \text{if } X[i - 1] \neq Y[j - 1] \end{cases} \)

3.3 Python 代码实现

def longest_common_subsequence(X, Y):

m = len(X)

n = len(Y)

# 创建二维数组dp并初始化边界条件

dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

for i in range(1, m + 1):

for j in range(1, n + 1):

if X[i - 1] == Y[j - 1]:

dp[i][j] = dp[i - 1][j - 1] + 1

else:

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

return dp[m][n]

# 示例数据

X = [1, 3, 4, 5, 6, 7, 7, 8]

Y = [3, 5, 7, 4, 8, 6, 7, 8, 2]

print(longest_common_subsequence(X, Y))

代码解释：

• X和Y分别是两个输入的序列。

• dp是一个二维列表，dp[i][j]表示序列X的前i个元素和序列Y的前j个元素的最长公共子序列的长度，初始化dp数组，所有元素初始化为 0 。

• 外层循环遍历序列X的元素，内层循环遍历序列Y的元素。

• 根据状态转移方程更新dp[i][j]的值。

• 最后返回dp[m][n]，即序列X和序列Y的最长公共子序列的长度。

3.4 代码分析与应用场景

• 时间复杂度：代码中有两层嵌套循环，外层循环遍历序列X的长度m次，内层循环遍历序列Y的长度n次，所以时间复杂度为\(O(m \times n)\) ，其中m和n分别是两个序列的长度。

• 空间复杂度：使用了一个二维数组dp，大小为\((m + 1) \times (n + 1)\)，所以空间复杂度为\(O(m \times n)\) 。同样，也可以使用滚动数组将空间复杂度优化到\(O(\min(m, n))\)。

应用场景：

• 文本比较：在版本控制系统中，如 Git，用于比较文件的不同版本，找出修改的部分。比如一个文件在不同时间有不同的版本，通过 LCS 算法可以确定哪些行被修改、删除或添加 。

• DNA 序列分析：生物信息学中，通过比较不同物种的 DNA 序列的最长公共子序列，来研究物种之间的进化关系和相似度。例如比较人类和黑猩猩的 DNA 序列，分析它们的相似程度 。

• 字符串匹配：在搜索引擎中，判断用户输入的关键词与文档内容的相关性，也可以用到最长公共子序列的思想。

四、典型实例 3：最长回文子串

4.1 问题描述

最长回文子串问题是指在一个给定的字符串中，找出其中最长的回文子串。回文串是指从左到右和从右到左读都一样的字符串，比如 “aba”“abba” 等 。例如，对于字符串 “babad”，其最长回文子串是 “bab” 或 “aba”；对于字符串 “cbbd”，最长回文子串是 “bb” 。

4.2 状态定义与转移方程

• 状态定义：定义dp[i][j]为一个布尔值，表示字符串s中从索引i到索引j的子串是否是回文串。

• 状态转移方程推导：

• • 当i == j时，即子串只有一个字符，显然是回文串，所以dp[i][i] = True 。例如字符串 “a”，它本身就是回文串。

• • 当j == i + 1时，即子串有两个字符，如果这两个字符相等，那么就是回文串，即dp[i][j] = (s[i] == s[j]) 。比如字符串 “aa”，dp[0][1]为True，而 “ab” 的dp[0][1]为False。

当j > i + 1时，如果s[i] == s[j]且dp[i + 1][j - 1]为True，那么dp[i][j]为True，否则为False。例如字符串 “abcba”，当判断 “abcba” 是否为回文串时，首先看首尾字符a是否相等，然后看去掉首尾字符后的 “bcb”（即dp[1][3]）是否为回文串，如果 “bcb” 是回文串，那么 “abcba” 就是回文串 。状态转移方程可以表示为：\( dp[i][j] = \begin{cases} True & \text{if } i = j \\ (s[i] == s[j]) & \text{if } j = i + 1 \\ (s[i] == s[j]) \land dp[i + 1][j - 1] & \text{if } j > i + 1 \end{cases} \)

4.3 Python 代码实现

def longest_palindromic_substring(s):

n = len(s)

if n < 2:

return s

# 创建二维数组dp并初始化边界条件

dp = [[False for _ in range(n)] for _ in range(n)]

max_length = 1

start = 0

# 初始化长度为1的子串

for i in range(n):

dp[i][i] = True

# 初始化长度为2的子串

for i in range(n - 1):

if s[i] == s[i + 1]:

dp[i][i + 1] = True

max_length = 2

start = i

# 动态规划填表

for length in range(3, n + 1):

for i in range(n - length + 1):

j = i + length - 1

if s[i] == s[j] and dp[i + 1][j - 1]:

dp[i][j] = True

max_length = length

start = i

return s[start:start + max_length]

# 示例数据

s = "babad"

print(longest_palindromic_substring(s))

代码解释：

• 首先获取字符串s的长度n，如果长度小于 2，直接返回原字符串。

• 创建二维布尔数组dp，dp[i][j]表示字符串s中从索引i到索引j的子串是否是回文串，初始值都为False。

• 初始化长度为 1 和 2 的子串的dp值。

• 通过两层循环，外层循环控制子串长度，内层循环控制子串起始位置，根据状态转移方程更新dp数组。

• 记录最长回文子串的起始位置start和长度max_length ，最后返回最长回文子串。

4.4 代码分析与优化思路

• 时间复杂度：代码中有三层循环，虽然其中一个循环的操作比较简单，但整体上时间复杂度主要由两层嵌套循环决定，外层循环遍历子串长度，最多执行n次，内层循环遍历子串起始位置，最多也执行n次，所以时间复杂度为\(O(n^2)\) ，其中n是字符串的长度。

• 空间复杂度：使用了一个二维数组dp，大小为\(n \times n\)，所以空间复杂度为\(O(n^2)\) 。

优化思路：

• 空间优化：可以使用中心扩展算法来降低空间复杂度。中心扩展算法的思路是，从字符串的每个字符开始，向两边扩展来判断是否为回文串，因为只需要在扩展过程中记录当前回文串的长度和起始位置，不需要像动态规划那样保存所有子串的状态，所以空间复杂度为\(O(1)\) 。具体实现如下：

def longest_palindromic_substring_optimized(s):

n = len(s)

if n < 2:

return s

start, max_length = 0, 1

def expand_around_center(left, right):

while left >= 0 and right < n and s[left] == s[right]:

left -= 1

right += 1

return right - left - 1

for i in range(n):

len1 = expand_around_center(i, i)

len2 = expand_around_center(i, i + 1)

max_len = max(len1, len2)

if max_len > max_length:

max_length = max_len

start = i - (max_len - 1) // 2

return s[start:start + max_length]

# 示例数据

s = "babad"

print(longest_palindromic_substring_optimized(s))

• Manacher 算法：进一步优化时间复杂度，可以使用 Manacher 算法，它的时间复杂度为\(O(n)\) 。该算法通过在字符串中插入特殊字符（如 “#”），将所有回文串都转化为奇数长度的回文串，然后利用回文串的对称性来快速计算每个位置的回文半径，从而找到最长回文子串。不过，Manacher 算法的实现相对复杂一些 。

五、总结与拓展

5.1 动态规划算法总结

动态规划算法作为一种强大的解题工具，其核心要点在于巧妙地利用问题的结构特性，将复杂问题拆解为可管理的子问题。通过精心定义状态和状态转移方程，我们能够高效地求解原本棘手的问题。在解决实际问题时，关键步骤如下：

1. 分析问题特性：仔细判断问题是否具备最优子结构和重叠子问题的特性。最优子结构意味着问题的最优解可以由子问题的最优解构建，这为我们提供了一种递归求解的思路；重叠子问题则表明在求解过程中，相同的子问题会多次出现，这是动态规划算法能够发挥优势的基础，通过存储子问题的解，我们可以避免重复计算，从而大大提高算法效率。

1. 精准定义状态：这是动态规划的关键环节。状态定义要能够准确、简洁地描述子问题，以便后续构建状态转移方程。一个好的状态定义应该能够覆盖问题的所有可能情况，并且便于理解和操作。例如在 0 - 1 背包问题中，定义dp[i][j]表示考虑前i个物品，背包容量为j时的最大价值，这个定义清晰地刻画了问题在不同阶段的状态，为后续的计算提供了明确的方向。

1. 构建状态转移方程：基于最优子结构特性，找出不同状态之间的递推关系，即状态转移方程。这是动态规划的核心，它描述了如何从已知状态推导出新的状态。在构建状态转移方程时，需要全面考虑各种可能的情况，确保方程的正确性和完整性。比如在最长公共子序列问题中，根据两个序列当前字符是否相等，分别给出了不同的状态转移方式，从而准确地计算出最长公共子序列的长度。

1. 妥善处理初始化和边界条件：初始化是动态规划计算的起点，边界条件则决定了计算的终止情况。正确设置初始化和边界条件对于得到正确的结果至关重要。例如在最长回文子串问题中，我们先初始化长度为 1 和 2 的子串的回文状态，为后续更长子串的判断提供了基础。

1. 高效实现与优化：根据状态转移方程，选择合适的数据结构和算法实现动态规划。在实现过程中，要注意代码的可读性和效率。同时，还可以通过空间优化、时间优化等技巧进一步提升算法性能。比如在 0 - 1 背包问题和最长公共子序列问题中，我们都探讨了如何使用滚动数组进行空间优化，减少内存消耗。

5.2 拓展学习建议

动态规划算法应用广泛且博大精深，想要深入掌握它，读者可以从以下几个方面进一步拓展学习：

• 深入研究经典问题：除了本文介绍的 0 - 1 背包问题、最长公共子序列和最长回文子串问题外，还有许多其他经典的动态规划问题，如最长递增子序列（LIS）、最大子数组和、矩阵链乘法、编辑距离等。深入研究这些问题，有助于加深对动态规划思想的理解和应用能力。例如，在最长递增子序列问题中，通过分析状态定义和状态转移方程的构建过程，可以学习到如何处理序列中元素的递增关系；在编辑距离问题中，能够了解如何通过动态规划计算两个字符串之间的相似度，这些问题都具有很强的代表性和实用性。

• 探索实际应用场景：动态规划在现实生活中有众多应用，如资源分配、任务调度、图像处理、生物信息学、金融分析等领域。尝试将动态规划算法应用到实际问题中，不仅可以提高解决实际问题的能力，还能更好地理解算法的价值和意义。比如在资源分配问题中，如何根据不同资源的成本和收益，利用动态规划实现资源的最优分配，以达到最大的效益；在任务调度问题中，如何考虑任务之间的依赖关系和时间限制，运用动态规划制定合理的调度方案，提高工作效率。

• 学习高级优化技巧：除了常见的空间优化和时间优化技巧外，还有一些更高级的优化方法，如状态压缩、四边形不等式优化等。学习这些优化技巧，可以进一步提升算法的性能，解决更复杂的问题。例如，在一些状态变量较多且取值范围有限的问题中，使用状态压缩技巧可以将多个状态变量压缩成一个整数，通过位运算来处理状态转移，从而大大减少空间复杂度；四边形不等式优化则适用于一些满足特定条件的动态规划问题，通过利用四边形不等式的性质，可以降低状态转移方程的计算复杂度，提高算法效率。

• 参考优质学习资源：推荐阅读相关的算法书籍，如《算法导论》《动态规划：从入门到实践》等，这些书籍对动态规划算法进行了系统而深入的讲解，包含丰富的理论知识和实际案例。在线学习平台也是很好的学习资源，如 LeetCode、力扣、牛客网等，上面有大量的动态规划练习题和题解，通过练习和学习他人的解题思路，可以不断提升自己的编程能力和思维水平。此外，一些知名的算法博客和技术论坛，如 CSDN 博客、知乎等，也有很多关于动态规划的优质文章和讨论，读者可以从中获取最新的算法知识和解题技巧。