本文将以动态规划（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] 的值即可。
原创文章，作者：JBLBB，如若转载，请注明出处：https://www.506064.com/n/373522.html
微信扫一扫 
支付宝扫一扫 