编写动态算法

6.1 开发动态算法的基本步骤。

开发动态算法的基本步骤

1. 确定子问题：

把问题分解成可以独立解决的较小子问题。这些子问题应该是重叠的，以便可以利用之前计算的结果。

2. 确定状态：

确定解决问题时可能出现的所有状态。状态应该描述从一个步骤到下一个步骤所需的全部信息。

3. 制定递推关系：

确定当前状态的问题解如何依赖于之前状态的解决方案。这个关系应该表达如何使用子问题的解来获得最优解。

4. 确定基本情况：

确定无需进一步计算即可直接知道其解的基本情况。

5. 填写表格：

创建一个表（通常是数组或矩阵）来存储所有子问题的解。使用递推关系和基本情况从下到上或从上到下填写表格。

6. 优化（备忘录）：

如果使用递归方法，请添加备忘录以保存子问题的结果，避免重复计算。

动态算法的时间复杂度和空间复杂度

时间复杂度：

• 动态算法的时间复杂度通常通过子问题的数量和计算每个子问题所需的时间来表达。
• 大多数情况下，时间复杂度是 O(n) 或 O(n^2)，其中 n 是输入数据的大小。

空间复杂度：

• 空间复杂度取决于需要存储的状态数量。
• 在某些情况下，可以通过优化（如减少到 O(n) 或 O(1) 的内存使用）来降低空间复杂度。

6.2 背包问题。

背包问题是一个 经典的组合优化问题，在计算机科学、经济学和物流管理等领域都存在。问题的主要目标是最大限度地利用有限资源。

背包问题的描述

有一个背包，能够承载一定的重量 W。还有 n 个物品，每个物品都有一定的重量 wt[i] 和价值 val[i]。 需要确定选择哪些物品以在不超过背包重量容量的情况下，使物品的总价值最大化。

背包问题的种类

1. 0/1 背包问题 (0/1 Knapsack Problem):

每个物品可以选择拿或不拿（不能部分拿）。

2. 分数背包问题 (Fractional Knapsack Problem):

每个物品可以拆分，拿其任意一部分。

3. 多重背包问题 (Multiple Knapsack Problem):

拥有几个不同重量限制的背包。

0/1 背包问题的算法术语表述：

递推关系：

对于每个物品 i 和每个可能的重量 w（从0到W）， 最优解可以如下表达：

• 如果物品 i 不放入背包，则最优价值等于前 i − 1 个物品和重量 w 的最优价值。
• 如果物品 i 放入背包，则最优价值等于该物品的价值加上前 i − 1 个物品和重量 w − wt[i] 的最优价值。

时间和空间复杂度

时间复杂度：

该算法的时间复杂度为 O(nW)，其中 n 是物品数量， W 是背包的容量。这是因为需要填充一个大小为 n × W 的表。

空间复杂度：

空间复杂度同样为 O(nW)，因为需要一个表来存储中间结果。

0/1 背包问题的实现示例

def knapsack(W, wt, val, n):
    # 创建表以存储中间值
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # 从下到上填充 dp 表
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# 使用示例
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"背包的最大价值: {knapsack(W, wt, val, n)}")
        

6.3 零钱兑换问题。

零钱兑换问题是一个 经典的动态规划问题，其目的是找到最少数量的硬币或找到组成特定金额的不同组合方式。这个问题有两个主要变种：

最少硬币数量 (Minimum Coin Change Problem):

找到构成目标总金额所需的最小硬币数量。

组合方式数量 (Number of Ways to Make Change):

找到用给定硬币集合组成目标金额的不同方式数。

变种 1. 最少硬币数量

问题描述

给定：

• 具有特定面值的无限硬币集合。
• 目标总金额 S。

要求：

• 找出构成总金额 S 所需的最小硬币数量。

使用动态规划的解决方案

递推关系：

• 设 dp[i] 是构成金额 i 所需的最小硬币数量。
• 对于每个硬币 c，如果 i ≥ c，则： dp[i] = min(dp[i], dp[i − c] + 1)

基本情况：

• dp[0] = 0（对于金额 0 需要 0 个硬币）。

时间和空间复杂度：

• 时间复杂度： O(n ⋅ S)，其中 n 是硬币面值的数量， S 是目标金额。
• 空间复杂度： O(S)，因为需要一个数组存储从 0 到 S 的每个金额所需的最小硬币数量。

Python 实现示例

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# 使用示例
coins = [1, 2, 5]
S = 11
print(f"金额 {S} 的最少硬币数量: {min_coins(coins, S)}")
        
        

零钱兑换问题展示了动态规划的灵活性。它用于教学和研究算法技术，因为它展示了如何使用递推关系和基本情况来有效解决问题