8 动态规划进阶之经典动态规划问题解法

在上一篇中，我们探讨了动态规划的基本思想及其应用，今天我们将深入研究一些经典的动态规划问题解法。这些问题不仅可以帮助我们巩固对动态规划的理解，同时也为解决复杂问题提供了思路。

经典动态规划问题

1. 斐波那契数列

斐波那契数列是动态规划中最基础的例子，求解第 $n$ 个斐波那契数可以通过简单的递归实现，但其复杂度为指数级，这在较大的 $n$ 下效率极低。因此，我们可以使用动态规划优化这一过程。

解决方案：

使用一个数组 dp 来存储计算结果，从而避免重复计算：

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

在这里，时间复杂度为 $O(n)$，空间复杂度也是 $O(n)$。我们也可以进一步优化，将空间复杂度降低到 $O(1)$。只需保存前两个数即可：

def fibonacci_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

2. 最长公共子序列（LCS）

最常见的动态规划经典问题之一是最长公共子序列。给定两个字符串，LCS 问题的目标是找到它们之间的最长子序列。

定义状态：

• 令 dp[i][j] 表示字符串 $A$ 的前 $i$ 个字符与字符串 $B$ 的前 $j$ 个字符的最长公共子序列的长度。

转移方程：

• 如果 $A[i - 1] = B[j - 1]$，则 $dp[i][j] = dp[i - 1][j - 1] + 1$。
• 否则，$dp[i][j] = \max(dp[i - 1][j], dp[i][j - 1])$。

代码实现：

def lcs(A, B):
    m, n = len(A), len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[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. 0-1 背包问题

0-1 背包问题是经典的优化问题，目标是从一组物品中选择部分放入背包，使得背包中的物品总价值最大。每个物品只能选择一次。

定义状态：

• 令 dp[i][j] 表示前 $i$ 个物品放入容量为 $j$ 的背包所能获得的最大价值。

转移方程：

• $$ dp[i][j] = dp[i - 1][j] \quad (j < w[i]) $$
• $$ dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) \quad (j \geq w[i]) $$

代码实现：

def knapsack(weights, values, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(capacity + 1):
            if j < weights[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

4. 硬币变化问题

给定不同面额的硬币和一个总金额，求用这些硬币组成该金额的组合数。

定义状态：

• 令 dp[j] 表示金额为 $j$ 的组合数。

转移方程：

• $$ dp[j] += dp[j - coin] $$

代码实现：

def coin_change(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1  # 初始化，金额为 0 的组合数为 1

    for coin in coins:
        for j in range(coin, amount + 1):
            dp[j] += dp[j - coin]

    return dp[amount]

小结

通过上述经典动态规划问题的分析与解法，我们可以看到动态规划不仅是一种强大的技术，同时也是一种思维方式。在处理一类问题时，明确状态、状态转移方程以及初始条件是关键。在下一篇中，我们将进一步探讨状态压缩动态规划，这是一种利用状态压缩技术来降低空间复杂度的有效方法。希望大家继续关注！