第 58 课·动态规划进阶

钢条切割

rod-cuttingpricemaximize

第 58 课 - 钢条切割

📌 学习目标

通过本课学习，你将能够：

  1. 理解钢条切割问题的背景和实际应用场景
  2. 掌握动态规划解法的状态定义和状态转移方程
  3. 实现自顶向下（带记忆化递归）和自底向上（迭代）两种动态规划解法
  4. 分析算法复杂度并理解如何优化决策过程
  5. 解决变种问题如需要成本的切割方案

🧠 核心概念

问题描述

假设你是一家钢条切割公司的经理。你有一根长度为 n 英寸的钢条，以及一个不同长度的价格表。你的目标是：通过切割钢条（或者不切割）使总收益最大化。

# 价格表示例（长度为i的钢条价格为p[i]）
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]  # 索引0表示长度0（价格0）
# 意味着：
# 长度1 -> 1元
# 长度2 -> 5元
# 长度3 -> 8元
# ...

为什么使用动态规划？

钢条切割问题具有最优子结构：长度为 n 的钢条的最优切割方案可以通过长度小于 n 的钢条的最优方案组合而成。同时存在重叠子问题，适合用动态规划解决。

两种思考方式

  1. 自顶向下（带记忆化的递归）：

    • 从原问题出发，分解为子问题
    • 使用字典/数组缓存已解决的子问题结果

  2. 自底向上（迭代）：

    • 从最小的子问题开始，逐步构建到原问题
    • 使用表格存储中间结果

💻 代码示例

方法一：自顶向下（带记忆化递归）

def cut_rod_memoized(prices, n):
    """
    自顶向下的钢条切割解法（带记忆化）
    
    参数：
    prices - 价格列表，prices[i]表示长度为i的钢条价格
    n - 钢条总长度
    
    返回：
    最大收益
    """
    # 初始化记忆化数组，-1表示未计算
    memo = [-1] * (n + 1)
    
    def helper(length):
        # 基础情况：长度为0时收益为0
        if length == 0:
            return 0
        
        # 如果已经计算过，直接返回缓存结果
        if memo[length] != -1:
            return memo[length]
        
        max_revenue = 0
        
        # 尝试所有可能的第一次切割位置
        # i 表示第一次切割出的长度
        for i in range(1, length + 1):
            # 当前切割收益 = 第一段的价格 + 剩余部分的最优收益
            current_revenue = prices[i] + helper(length - i)
            max_revenue = max(max_revenue, current_revenue)
        
        # 缓存结果并返回
        memo[length] = max_revenue
        return max_revenue
    
    return helper(n)

# 测试
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
n = 10
print(f"长度为 {n} 的钢条最大收益: {cut_rod_memoized(prices, n)}")
# 输出：长度为 10 的钢条最大收益: 30

方法二：自底向上（迭代动态规划）

def cut_rod_dp(prices, n):
    """
    自底向上的钢条切割解法（迭代DP）
    
    参数：
    prices - 价格列表，prices[i]表示长度为i的钢条价格
    n - 钢条总长度
    
    返回：
    (最大收益, 切割方案列表)
    """
    # dp[i] 表示长度为i的钢条能获得的最大收益
    dp = [0] * (n + 1)
    
    # s[i] 表示达到dp[i]时第一次切割的长度
    s = [0] * (n + 1)
    
    # 从小到大计算每个长度的最优解
    for length in range(1, n + 1):
        max_revenue = 0
        
        # 尝试所有可能的第一次切割
        for i in range(1, length + 1):
            # 如果切割位置i有效
            if i < len(prices):
                current_revenue = prices[i] + dp[length - i]
                
                if current_revenue > max_revenue:
                    max_revenue = current_revenue
                    s[length] = i  # 记录最优切割决策
        
        dp[length] = max_revenue
    
    # 回溯找到具体切割方案
    cuts = []
    remaining = n
    while remaining > 0:
        cuts.append(s[remaining])
        remaining -= s[remaining]
    
    return dp[n], cuts

# 测试
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
n = 10
max_revenue, cuts = cut_rod_dp(prices, n)
print(f"长度为 {n} 的钢条最大收益: {max_revenue}")
print(f"切割方案（各段长度）: {cuts}")
# 输出：
# 长度为 10 的钢条最大收益: 30
# 切割方案（各段长度）: [10]

方法三：带成本的变种问题

def cut_rod_with_cost(prices, n, cut_cost):
    """
    带切割成本的钢条切割问题
    每次切割需要额外成本
    
    参数：
    prices - 价格列表
    n - 钢条总长度
    cut_cost - 每次切割的成本
    
    返回：
    最大收益
    """
    # dp[i] 表示长度为i的钢条能获得的最大收益（考虑切割成本）
    dp = [0] * (n + 1)
    
    for length in range(1, n + 1):
        # 选项1：不切割，直接卖
        dp[length] = prices[length] if length < len(prices) else 0
        
        # 选项2：尝试所有切割方式
        for i in range(1, length):
            # 切割成i和length-i两段，需要支付一次切割成本
            current_revenue = dp[i] + dp[length - i] - cut_cost
            dp[length] = max(dp[length], current_revenue)
    
    return dp[n]

# 测试
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
n = 10
cut_cost = 1  # 每次切割成本为1
max_revenue = cut_rod_with_cost(prices, n, cut_cost)
print(f"长度为 {n} 的钢条最大收益（考虑切割成本）: {max_revenue}")
# 输出：长度为 10 的钢条最大收益（考虑切割成本）: 29

🏋️ 实践练习

练习 1：基础实现

实现 cut_rod_simple 函数，返回长度为 n 的钢条的最大收益（不考虑切割方案）。

def cut_rod_simple(prices, n):
    """
    计算钢条切割的最大收益
    
    参数：
    prices - 价格列表，索引为长度，值为价格
    n - 钢条长度
    
    返回：
    最大收益
    """
    # 你的代码在这里
    pass

# 测试用例
prices = [0, 1, 5, 8, 9, 10]
print(cut_rod_simple(prices, 5))  # 期望输出: 13
print(cut_rod_simple(prices, 4))  # 期望输出: 10

练习 2：获取切割方案

修改你的代码，使其不仅返回最大收益，还返回具体的切割方案（各段长度列表）。

def cut_rod_with_solution(prices, n):
    """
    计算钢条切割的最大收益和具体切割方案
    
    返回：
    (最大收益, 切割方案列表)
    """
    # 你的代码在这里
    pass

# 测试用例
prices = [0, 1, 5, 8, 9, 10]
max_revenue, cuts = cut_rod_with_solution(prices, 5)
print(f"最大收益: {max_revenue}")  # 期望输出: 13
print(f"切割方案: {cuts}")        # 期望输出: [2, 3] 或 [3, 2]

练习 3：变种问题 - 不同价格表

假设有两家公司收购钢条，价格表不同。如何选择使收益最大化？

def cut_rod_two_companies(prices1, prices2, n):
    """
    两家公司不同价格表，选择收益更高的
    
    参数：
    prices1, prices2 - 两个公司的价格表
    n - 钢条长度
    
    返回：
    最大收益
    """
    # 你的代码在这里
    pass

# 测试用例
prices1 = [0, 1, 5, 8, 9, 10]
prices2 = [0, 2, 4, 7, 8, 12]
print(cut_rod_two_companies(prices1, prices2, 5))  # 期望输出: 13（来自第一家公司）

⚠️ 常见错误

  1. 价格列表索引错误：价格列表的索引应该从0开始，prices[0]通常为0（表示长度为0的钢条价格为0）。

  2. 边界条件处理不当：忘记处理长度为0的情况，或尝试访问价格列表之外的索引。

  3. 记忆化数组初始化错误：初始化记忆化数组时，应使用特殊值（如-1）表示未计算，而不是0（因为0可能是有效结果）。

  4. 状态转移方程理解错误：记住状态转移方程是：

    dp[n] = max{price[i] + dp[n-i]} for i = 1 to n

    其中 price[i] 是长度为 i 的钢条价格。

  5. 切割方案回溯错误：在记录最优决策时，要正确记录第一次切割的长度，回溯时才能得到正确的切割方案。

📝 小结

关键要点：

  1. 问题本质：钢条切割问题是动态规划经典问题，具有最优子结构和重叠子问题特性。

  2. 状态定义：dp[i] 表示长度为 i 的钢条能获得的最大收益。

  3. 状态转移：

    dp[i] = max(price[j] + dp[i-j]) for j = 1 to i

  4. 两种解法：

    • 自顶向下（带记忆化的递归）：直观易理解，但递归深度可能较大
    • 自底向上（迭代DP）：效率更高，空间可优化

  5. 空间优化：实际上，可以只用一维数组存储DP结果，因为每次计算只依赖更小的子问题。

  6. 变种扩展：

    • 带切割成本：每次切割需要额外费用
    • 多价格表：不同买家给出不同价格
    • 不同切割限制：如最多切割次数限制

动态规划思维：

  • 识别问题是否具有最优子结构
  • 定义清晰的状态和状态转移方程
  • 考虑是自顶向下还是自底向上更合适
  • 分析时间复杂度：通常是 O(n²)

下一课我们将学习区间DP，这是一种处理区间相关问题的动态规划方法，适用于矩阵链乘法、石子合并等问题。

练习编辑器

rust
Loading...

继续学习

完成本课后，建议继续学习下一课「区间 DP」 以巩固所学知识。