本文将以动态规划(Dynamic Programming, DP)例题为中心,深入阐述动态规划的原理和应用。
一、最长公共子序列问题
最长公共子序列问题(Longest Common Subsequence, LCS)是一道经典的动态规划问题。给定两个字符串 s1 和 s2,找到它们之间最长的公共子序列(可以不连续)。
在解决这个问题时,我们可以使用二维数组 dp 来进行动态规划。数组 dp 中的 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符之间的最长公共子序列长度。下面是对应的 Python 代码:
def longestCommonSubsequence(s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[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]
在这段代码中,我们首先定义了两个字符串 s1 和 s2 的长度 m 和 n。然后使用一个二维数组 dp 来存储动态规划的结果。接着我们进行两层 for 循环,枚举 s1 和 s2 的所有情况。对于每一个状态 dp[i][j],如果 s1[i-1] 等于 s2[j-1],那么当前位置的最长公共子序列长度就为 dp[i-1][j-1] + 1,否则就为 max(dp[i-1][j], dp[i][j-1])。最后,我们返回 dp[m][n] 的值即可。
二、0/1背包问题
0/1背包问题(0/1 Knapsack Problem)也是一道经典的动态规划问题。给定一个背包容量和若干个物品,每个物品有两个属性:重量和价值。要求在不超过背包容量的情况下,选择一些物品装入背包,使得背包中物品的总价值最大。
我们同样可以使用二维数组 dp 来进行动态规划。数组 dp 中的 dp[i][j] 表示在前 i 个物品中,容量不超过 j 的情况下,选择物品的最大价值。下面是对应的 Python 代码:
def knapsack(w: List[int], v: List[int], c: int) -> int:
n = len(w)
dp = [[0] * (c + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, c + 1):
if j < w[i - 1]:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
return dp[n][c]
在这段代码中,我们同样定义了物品的重量 w、价值 v,以及背包的容量 c。然后使用一个二维数组 dp 来存储动态规划的结果。接着我们进行两层 for 循环,枚举前 i 个物品以及不同的容量情况。对于每一个状态 dp[i][j],如果当前物品的重量 w[i-1] 大于背包剩余容量 j,那么就不能选择该物品,当前状态的最大价值就等于上一个状态 dp[i-1][j] 的价值。否则,我们需要选择该物品,因此当前状态的最大价值就等于 dp[i-1][j-w[i-1]] + v[i-1] 和 dp[i-1][j] 中的较大值。最后,我们返回 dp[n][c] 的值即可。
三、斐波那契数列问题
斐波那契数列(Fibonacci Sequence)也是一道常见的动态规划问题。斐波那契数列中的第 n 项可以用以下递归公式表示:
F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1
但是这种递归过程效率较低,因为在递归中会有大量重复计算。我们可以使用一个数组来记录已经计算好的中间值,以避免重复计算。下面是对应的 Python 代码:
def fib(n: int) -> int:
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
在这段代码中,我们先判断输入的 n 是否小于等于 1,如果是的话直接返回 n。否则,我们定义一个数组 dp 来记录已经计算好的中间值。数组 dp 中的 dp[i] 表示斐波那契数列中的第 i 项。接着,使用一个 for 循环进行动态规划计算。在这个 for 循环中,每次都将 dp[i] 的值更新为 dp[i-1] 和 dp[i-2] 的和。最后,我们返回 dp[n] 的值即可。