动态规划

简介

动态规划（dynamic programming）是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同。

• 分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。
• 动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。
• 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题。

实际上，动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构、无后效性。

区别点	动态规划（DP）	分治（Divide & Conquer）
核心思想	通过存储子问题结果，避免重复计算	将问题分解成多个独立的子问题递归求解
子问题是否重叠	是，同一个子问题可能被计算多次	否，子问题之间互不相交
是否有最优子结构	是，大问题的最优解可以由子问题的最优解构成	依赖于具体问题，通常具有
解法方式	自底向上，通常用递推（迭代）	自顶向下，通常用递归
时间复杂度优化	通过记忆化搜索（递归+缓存） 或 状态转移表（迭代） 降低复杂度	直接递归，可能导致重复计算
适用场景	最优化问题，如最长子序列、背包问题、编辑距离	适用于能被分割成独立子问题的问题，如归并排序、二分搜索、快速排序

常见问题

0-1背包问题

给定一个容量为 W 的背包和 n 个物品，每个物品有一个重量 w[i] 和价值 v[i]。你要选择放入哪些物品，使得总重量 <= W，并且总价值最大。

注意：每个物品只能取 0（不放）或 1（放入），不能拆分。

def knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
    """0-1 背包：动态规划"""
    n = len(wgt)
    # 初始化 dp 表
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    # 状态转移
    for i in range(1, n + 1):
        for c in range(1, cap + 1):
            if wgt[i - 1] > c:
                # 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c]
            else:
                # 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
    return dp[n][cap]


"""Driver Code"""
if __name__ == "__main__":
    wgt = [10, 20, 30, 40, 50]
    val = [50, 120, 150, 210, 240]
    cap = 50
    n = len(wgt)

    # 动态规划
    res = knapsack_dp(wgt, val, cap)
    print(f"不超过背包容量的最大物品价值为 {res}")