算法学习4——动态规划

动态规划（Dynamic Programming，简称DP）是一种用于解决具有重叠子问题和最优子结构性质的问题的算法设计技术。它通过将复杂问题分解为更小的子问题，并保存子问题的解来避免重复计算，从而提高算法的效率。

基本思想

动态规划的核心思想是将问题分解成子问题，并通过存储子问题的解来避免重复计算。这一思想可以通过两种方式实现：

1. 自顶向下的备忘录法（Top-Down with Memoization）：递归解决问题，并将已计算的结果存储在备忘录中，以便后续使用。
2. 自底向上的动态规划法（Bottom-Up Dynamic Programming）：从最小的子问题开始，逐步构建出较大的子问题的解。

步骤

1. 定义子问题：将原问题分解为若干个子问题。
2. 确定状态转移方程：找出子问题之间的关系，建立递推公式。
3. 确定初始条件和边界情况：设定最小子问题的解。
4. 自底向上计算：利用递推公式计算子问题的解，最终得到原问题的解。

经典问题及代码示例

下面是三个关于动态规划的经典问题，可以帮助理解动态规划这一概念。

1. 斐波那契数列

问题描述：斐波那契数列的定义如下：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。

动态规划实现步骤：

1. 定义子问题：F(n)表示第n个斐波那契数。
2. 确定状态转移方程：F(n) = F(n-1) + F(n-2)。
3. 确定初始条件和边界情况：F(0) = 0, F(1) = 1。
4. 自底向上计算：
   • 初始化一个数组dp，长度为n+1。
   • 将dp[0]设为0，dp[1]设为1。
   • 从2开始到n，逐步计算dp[i] = dp[i-1] + dp[i-2]。
   • 返回dp[n]。

Python代码：

def fibonacci(n):
    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]

# 示例
print(fibonacci(10))  # 输出 55

2. 最长公共子序列

问题描述：给定两个字符串，找到它们的最长公共子序列的长度。

动态规划实现步骤：

1. 定义子问题：设dp[i][j]表示text1[0]和text2[0]的最长公共子序列长度。
2. 确定状态转移方程：
   • 如果text1[i-1] == text2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1。
   • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
3. 确定初始条件和边界情况：dp[0][]和dp[][0]均为0，因为空字符串的最长公共子序列长度为0。
4. 自底向上计算：
   • 初始化一个二维数组dp，大小为(m+1) x (n+1)。
   • 遍历所有i和j，根据状态转移方程更新dp[i][j]。
   • 最终返回dp[m][n]。

Python代码：

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]

# 示例
text1 = "abcde"
text2 = "ace"
print(longest_common_subsequence(text1, text2))  # 输出 3

3. 0/1 背包问题

问题描述：给定一组物品，每个物品有一个重量和一个价值，在满足背包容量限制的情况下，选择物品使得总价值最大。

动态规划实现步骤：

1. 定义子问题：设dp[i][w]表示前i个物品在容量为w的背包中的最大价值。
2. 确定状态转移方程：
   • 如果第i个物品的重量小于等于w，则dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])。
   • 否则，dp[i][w] = dp[i-1][w]。
3. 确定初始条件和边界情况：dp[0][]和dp[][0]均为0，因为没有物品或容量为0时，最大价值为0。
4. 自底向上计算：
   • 初始化一个二维数组dp，大小为(n+1) x (capacity+1)。
   • 遍历所有i和w，根据状态转移方程更新dp[i][w]。
   • 最终返回dp[n][capacity]。

Python代码：

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, 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]

# 示例
weights = [1, 2, 3]
values = [10, 15, 40]
capacity = 5
print(knapsack(weights, values, capacity))  # 输出 55

总结

动态规划是一种强大的算法设计技术，适用于解决许多复杂的最优化问题。通过将问题分解为子问题，并利用存储子问题解的方式来避免重复计算，动态规划可以显著提高计算效率。本文介绍了动态规划的基本思想、实现步骤，以及几个经典问题的Python代码示例。掌握动态规划技巧，将有助于你在编程竞赛和实际项目中解决更多复杂的问题