本文深入探讨了动态规划进阶的相关内容，涵盖了动态规划的基本概念、核心思想以及与递归的区别。文章还详细介绍了几种常见的动态规划问题类型，如最优化问题、子序列问题和背包问题，并通过示例代码进行了说明。此外，文章还讨论了动态规划的求解步骤和优化技巧，帮助读者更好地理解和应用动态规划进阶知识。
动态规划基础回顾 动态规划的基本概念动态规划(Dynamic Programming)是一种通过将复杂问题分解为更小的子问题来解决的方法。这种方法通常用于解决最优化问题，即在给定一系列决策的情况下找到最优解。动态规划利用了问题的重叠子问题性质，也即解决大问题时会不断遇到子问题。在每个子问题上应用相同的策略，从而避免了重复计算，大大提高了效率。
动态规划通过存储子问题的答案来避免重复计算。这种特性使动态规划在处理大规模问题时非常有效。其基本思想是通过缓存中间结果来减少不必要的计算，从而实现高效解题。
动态规划可以应用于许多领域，包括但不限于计算机科学中的算法设计、数学中的组合优化、经济学中的资源分配等。
动态规划的核心思想动态规划的核心思想是将一个大问题分解为多个小问题，通过解决这些小问题来间接解决大问题。具体步骤包括识别问题的子结构，定义子问题的解，并建立子问题之间相互依赖的关系。以下是一些关键概念：
-
最优子结构：如果一个大问题的最优解可以通过它的子问题的最优解来构建，那么该问题具备最优子结构。
-
重叠子问题：解决一个大问题会反复遇到相同的子问题。动态规划通过存储每个子问题的解来避免重复计算，从而提高效率。
-
状态定义：定义每个子问题的状态，通常用变量表示。状态表示的是问题的一个特定情况或条件。
- 状态转移：通过状态转移方程，将一个状态的解转换为另一个状态的解。状态转移方程描述了状态之间的转换关系。
动态规划与递归有密切的关系。递归是一种通过不断调用自身来解决问题的方法，而动态规划则是在递归的基础上进行了优化。两者的区别在于：
-
递归：递归方法直接通过函数调用自身来解决问题，通常不需要额外的存储机制来存储中间结果。递归方法可能会导致大量的重复计算，从而降低效率。
- 动态规划：动态规划在递归的基础上引入了存储中间结果的机制，使得每个子问题只计算一次。这种方法大大提高了效率，尤其是在处理具有重叠子问题的问题时。
动态规划通常通过两种方式实现：
-
自顶向下：从原始问题开始，递归地分解问题，并在递归调用时缓存中间结果。这种方法称为记忆化搜索，其核心是使用缓存来存储子问题的解。
- 自底向上：从最简单的问题开始，逐步构建更大问题的解。这种方法通常使用循环来实现，且需要一个数组或表格来存储子问题的解。
下面是一个简单的例子来说明这两者的区别：
示例代码
下面是斐波那契数列的递归实现，不使用缓存：
def fib_recursive(n):
if n <= 1:
return n
else:
return fib_recursive(n - 1) + fib_recursive(n - 2)下面是斐波那契数列的动态规划实现，使用缓存：
def fib_dp(n):
if n <= 1:
return n
# 利用缓存存储中间结果
cache = [0] * (n + 1)
cache[0] = 0
cache[1] = 1
for i in range(2, n + 1):
cache[i] = cache[i - 1] + cache[i - 2]
return cache[n]递归版本在计算较大的斐波那契数时会出现大量重复计算，而动态规划版本则通过缓存中间结果避免了这种重复计算。
常见动态规划问题类型动态规划可以应用于多种问题类型，以下是几种常见的动态规划问题：
- 最优化问题：如最短路径问题、最长递增子序列问题等。
- 子序列问题：如最长公共子序列问题、最长递增子序列问题等。
- 背包问题：如0-1背包问题、完全背包问题等。
最优化问题通常涉及找到最优解。例如，最短路径问题是在给定的图中找到从一个节点到另一个节点的最短路径。动态规划通过将问题分解为一系列子问题，从局部最优解构建全局最优解。
示例代码
以下是一个简单的最短路径问题的动态规划实现：
def shortest_path(graph, source, destination):
# 初始化距离数组
distances = [float('inf')] * len(graph)
distances[source] = 0
# 处理每个节点
for _ in range(len(graph) - 1):
for node in range(len(graph)):
for neighbor in range(len(graph)):
if graph[node][neighbor] != 0 and distances[node] + graph[node][neighbor] < distances[neighbor]:
distances[neighbor] = distances[node] + graph[node][neighbor]
return distances[destination]子序列问题通常涉及在给定序列中找到特定的子序列，例如最长递增子序列问题。动态规划通过构造子序列的不同前缀来解决这类问题。
示例代码
以下是一个最长递增子序列问题的动态规划实现：
def longest_increasing_subsequence(arr):
n = len(arr)
lis = [1] * n
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j] + 1
return max(lis)背包问题是一种典型的动态规划问题，通常包括0-1背包问题和完全背包问题。0-1背包问题每个物品只能选择一次，而完全背包问题每个物品可以选择多次。
示例代码
以下是一个简单的0-1背包问题的动态规划实现：
def knapsack_01(capacity, weights, values, n):
# 创建一个二维数组来存储子问题的结果
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]动态规划问题的求解通常遵循以下几个步骤：
-
确定状态：定义问题的状态，即问题的各个阶段和变量。状态通常用变量来表示，例如在背包问题中，状态可以表示为剩余容量和已经选择的物品。
-
确定选择：确定每种状态下可以进行的选择，例如在背包问题中，可以选择将某个物品放入背包，或者不放入。
-
明确状态转移方程：通过状态转移方程，将一个状态的解转换为另一个状态的解。状态转移方程通常表示为递推公式。
- 计算顺序：确定计算状态的顺序，通常是按状态变量的顺序进行计算。例如，在背包问题中，可以按物品的顺序进行计算。
通过这些步骤，我们可以系统地解决动态规划问题，避免遗漏任何可能的状态和选择。
示例代码
以下是一个简单的背包问题的状态转移方程示例：
def knapsack_01(capacity, weights, values, n):
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]在这个例子中，dp[i][w] 表示在前 i 个物品中，总重量不超过 w 的最大价值。状态转移方程为：
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) if weights[i - 1] <= w else dp[i - 1][w]通过这个状态转移方程，我们可以从较小的问题逐步构建到较大的问题。
动态规划中的优化技巧动态规划在处理大规模问题时可能会遇到内存和时间上的限制。以下是一些常见的优化技巧：
- 空间优化：减少动态规划所需的内存空间
- 时间优化：提高动态规划的执行效率
- 记忆化搜索：通过缓存中间结果避免重复计算
空间优化通常通过减少存储中间结果的空间来实现。例如，可以使用滚动数组来存储最近的状态，而不是保存所有状态。
示例代码
以下是一个使用滚动数组优化的背包问题实现：
def knapsack_01(capacity, weights, values, n):
dp = [0] * (capacity + 1)
for i in range(1, n + 1):
for w in range(capacity, weights[i - 1] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i - 1]] + values[i - 1])
return dp[capacity]在这个例子中，我们使用了一个长度为 capacity + 1 的数组 dp 来存储当前状态的结果。通过从右向左更新数组，避免了覆盖尚未使用的状态。
时间优化通常通过减少不必要的计算来实现。例如，可以通过剪枝或提前终止来减少不必要的递归调用。
示例代码
以下是一个通过剪枝优化的递归实现：
def knapsack_01(capacity, weights, values, n, index=0):
if index >= n or capacity <= 0:
return 0
if weights[index] > capacity:
return knapsack_01(capacity, weights, values, n, index + 1)
return max(
values[index] + knapsack_01(capacity - weights[index], weights, values, n, index + 1),
knapsack_01(capacity, weights, values, n, index + 1)
)在这个例子中，我们通过剪枝来避免不必要的递归调用，即如果当前物品的重量大于剩余容量，则直接跳过该物品。
记忆化搜索记忆化搜索通过缓存中间结果来避免重复计算。通常通过使用缓存或缓存装饰器来实现。
示例代码
以下是一个使用缓存的递归实现：
from functools import lru_cache
@lru_cache(None)
def knapsack_01(capacity, weights, values, n, index=0):
if index >= n or capacity <= 0:
return 0
if weights[index] > capacity:
return knapsack_01(capacity, weights, values, n, index + 1)
return max(
values[index] + knapsack_01(capacity - weights[index], weights, values, n, index + 1),
knapsack_01(capacity, weights, values, n, index + 1)
)在这个例子中，我们使用了 lru_cache 装饰器来缓存中间结果，避免了重复计算。
最长递增子序列问题
最长递增子序列问题是在给定序列中找到最长的递增子序列。例如，给定序列 arr = [10, 9, 2, 5, 3, 7, 101, 18]，最长递增子序列是 [2, 3, 7, 101]。
示例代码
以下是一个最长递增子序列问题的动态规划实现：
def longest_increasing_subsequence(arr):
n = len(arr)
lis = [1] * n
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j] + 1
return max(lis)在这个例子中，我们使用了一个数组 lis 来存储每个位置的最长递增子序列长度。状态转移方程为：
lis[i] = max(lis[j] + 1) if arr[i] > arr[j] and lis[i] < lis[j] + 1对于最长递增子序列问题，我们可以使用多种解法来实现。以下是一些常见的解法：
解法1：动态规划
我们已经介绍了使用动态规划的实现方法。
解法2：二分查找
使用二分查找来维护一个递增子序列，从而找到最长递增子序列。这种方法的时间复杂度为 O(n log n)。
示例代码
以下是一个使用二分查找的实现：
def longest_increasing_subsequence(arr):
sub = []
for num in arr:
pos = bisect_left(sub, num)
if pos == len(sub):
sub.append(num)
else:
sub[pos] = num
return len(sub)在这个例子中，我们使用了 bisect_left 函数来找到合适的插入位置，并更新递增子序列。
对比
- 动态规划方法的时间复杂度为
O(n^2)，空间复杂度为O(n)。 - 二分查找方法的时间复杂度为
O(n log n)，空间复杂度为O(n)。
最长递增子序列问题可以扩展为：
- 最长递增子序列的长度。
- 最长递增子序列的具体序列。
- 最长递增子序列的数量。
示例代码
以下是一个寻找最长递增子序列的具体序列的实现：
def longest_increasing_subsequence(arr):
n = len(arr)
lis = [1] * n
prev = [-1] * n
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j] + 1
prev[i] = j
max_length = max(lis)
max_index = lis.index(max_length)
sequence = []
while max_index >= 0:
sequence.append(arr[max_index])
max_index = prev[max_index]
return max_length, sequence[::-1]在这个例子中，我们使用了一个数组 prev 来存储每个位置的前驱位置，从而构建最长递增子序列的具体序列。
-
爬楼梯问题：给定一个正整数 n，计算有多少种方法可以爬到楼顶。每次你可以爬 1 或 2 个台阶。
示例代码：
def climb_stairs(n): if n <= 1: return n dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] -
最长公共子序列问题：给定两个字符串
text1和text2，返回它们的最长公共子序列的长度。示例代码：
def longest_common_subsequence(text1, text2): m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[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] -
零钱兑换问题：给定不同面值的硬币，求组成指定金额的最少硬币数量。
示例代码：
def coin_change(amount, coins): dp = [0] + [float('inf')] * amount for coin in coins: for x in range(coin, amount + 1): dp[x] = min(dp[x], dp[x - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1
-
最长递增子序列问题：给定一个无序数组，返回最长递增子序列的长度。
示例代码：
def longest_increasing_subsequence(arr): n = len(arr) lis = [1] * n for i in range(1, n): for j in range(i): if arr[i] > arr[j] and lis[i] < lis[j] + 1: lis[i] = lis[j] + 1 return max(lis) -
最长公共子序列的修改版：给定两个字符串
text1和text2，返回它们的最长公共子序列的长度和具体的子序列。示例代码：
def longest_common_subsequence(text1, text2): m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] prev = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 prev[i][j] = 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) prev[i][j] = 2 if dp[i - 1][j] > dp[i][j - 1] else 3 i, j = m, n sequence = [] while i > 0 and j > 0: if prev[i][j] == 1: sequence.append(text1[i - 1]) i -= 1 j -= 1 elif prev[i][j] == 2: i -= 1 else: j -= 1 return dp[m][n], ''.join(sequence[::-1]) -
最小跳跃次数问题：给定一个非负整数数组
nums，从数组的起始位置开始跳跃，以最小的跳跃次数到达数组的最后一个位置。示例代码：
def jump(nums): n = len(nums) dp = [0] * n for i in range(1, n): dp[i] = float('inf') for j in range(i): if i <= j + nums[j] and dp[j] != float('inf'): dp[i] = min(dp[i], dp[j] + 1) return dp[n - 1]
示例1：爬楼梯问题
问题描述
给定一个正整数 n，计算有多少种方法可以爬到楼顶。每次你可以爬 1 或 2 个台阶。
解题思路
使用动态规划，定义 dp[i] 表示到达第 i 级台阶的方法数。状态转移方程为：
dp[i] = dp[i - 1] + dp[i - 2]示例代码
def climb_stairs(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]示例2：最长公共子序列问题
问题描述
给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。
解题思路
使用动态规划，定义 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。状态转移方程为：
dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) if text1[i - 1] != text2[j - 1]示例代码
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[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]示例3：零钱兑换问题
问题描述
给定不同面值的硬币，求组成指定金额的最少硬币数量。
解题思路
使用动态规划，定义 dp[i] 表示组成金额 i 的最少硬币数量。状态转移方程为：
dp[i] = min(dp[i - coin] + 1) for each coin in coins示例代码
def coin_change(amount, coins):
dp = [0] + [float('inf')] * amount
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1