动态规划

动态规划（Dynamic Programming）算法是一种将大问题分解为子问题的优化算法，其基本思想是将问题分解为子问题，分别求解子问题的最优解，最后将子问题的最优解组合成原问题的最优解。知识点：

  • 三要素：重叠子问题、最优子结构、状态转移方程
  • 实现：动态规划算法通常采用自底向上或自顶向下的方式进行求解。自底向上的方法需要先求解小规模的子问题，再根据子问题的解求解大规模的子问题，直至求解原问题。自顶向下的方法则是从原问题开始，逐步将问题分解为子问题，并通过记忆化搜索的方式将已经求解过的子问题记录下来，避免重复计算。即带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。
  • 应用：动态规划算法常用于求解具有重叠子问题和最优子结构的问题。如在路径规划、背包问题、编辑距离等领域。其中最经典的应用是背包问题，通过动态规划算法可以高效地求解背包问题的最优解。
  • 优化：动态规划算法的时间复杂度往往较高。常用的优化方法包括状态压缩、空间优化、滚动数组等。状态压缩可以将问题的状态表示压缩成一个整数或者一个二进制数，从而减少状态的存储空间。空间优化可以通过仅保存部分状态，避免保存所有状态，从而减少空间使用。滚动数组则是通过循环利用数组来减少空间使用。另外，在实际应用中可以根据问题的特点进行算法的优化，例如在路径规划中，可以使用A*算法等算法加速求解过程。
  • 类型题：都具有递推性质
    1. 求最优解，典型问题是背包问题，当前问题的最优解取决于子问题的最优解（最优子结构）。
    2. 计数类，如统计方案数的问题，当前问题的方案数取决于子问题的方案数。

遇到求最值的问题，基本都是由动态规划算法来解决

算法框架

  • 解决两个字符串的动态规划问题，一般都是用两个指针 i, j 分别指向两个字符串的最后，然后一步步往前移动，缩小问题的规模
  • 像子数组、子序列这类问题，你就可以尝试定义 dp[i] 是以 nums[i] 为结尾的最大子数组和/最长递增子序列，因为这样定义更容易将 dp[i+1] 和 dp[i] 建立起联系，利用数学归纳法写出状态转移方程
    1. 涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：在子数组arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列（最长公共子序列）长度为dp[i][j]。
    2. 只涉及一个字符串/数组时（比如本文要讲的最长回文子序列），dp 数组的含义如下：在子数组array[i..j]中，我们要求的子序列（最长回文子序列）的长度为dp[i][j]。

解题步骤：

  1. 确定 base case
  2. 确定「状态」，也就是原问题和子问题中会变化的变量
  3. 确定「选择」，也就是导致「状态」产生变化的行为
  4. 明确 dp 函数/数组的定义。根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0…i-1] 都已知，想办法求出 dp[i]，一旦这一步完成，整个题目基本就解决了。如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组
  5. 动态规划问题的最后一步优化，如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试缩小 DP table 的大小，只记录必要的数据，从而降低空间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

灵神数位DP

灵神换跟DP

灵神状压DP

力扣指南

动态规划
题目 技巧 难度
✅509. 斐波那契数 dp table记录重叠子问题 🌟
✅322. 零钱兑换 🌟🌟
✅72. 编辑距离 dp[i][j]表示长度为i的str1和长度为j的str2的最小编辑距离 🌟🌟🌟
✅300. 最长递增子序列 d[i]表示长度为i的最长上升子序列的末尾元素的最小值 🌟🌟
✅354. 俄罗斯套娃信封问题 二维转一维 🌟🌟🌟
❌✅53. 最大子数组和 滑动窗口、dp、前缀和 分治未解 🌟🌟
✅1143. 最长公共子序列 🌟🌟
✅5. 最长回文子串 🌟🌟
✅583. 两个字符串的删除操作 🌟🌟
✅712. 两个字符串的最小ASCII删除和 🌟🌟
✅1312. 让字符串成为回文串的最少插入次数 🌟🌟🌟
✅516. 最长回文子序列 画dp表 🌟🌟
✅62. 不同路径 🌟🌟
✅63. 不同路径 II 滚动数组不会 🌟🌟
✅64. 最小路径和 🌟🌟
✅931. 下降路径最小和 🌟🌟
✅174. 地下城游戏 反向DP 🌟🌟🌟
✅198. 打家劫舍 🌟🌟
✅213. 打家劫舍 II 分类讨论 🌟🌟
✅337. 打家劫舍 III 🌟🌟
✅121. 买卖股票的最佳时机 只购买一次 🌟
❌✅122. 买卖股票的最佳时机 II 贪心 无限次购买 🌟🌟
✅309. 最佳买卖股票时机含冷冻期 🌟🌟
✅714. 买卖股票的最佳时机含手续费 🌟🌟
✅123. 买卖股票的最佳时机 III 特定的买卖次数 🌟🌟🌟
✅188. 买卖股票的最佳时机 IV 买卖次数不限制 🌟🌟🌟
✅514. 自由之路 画dp表判断循环方向和顺序 🌟🌟🌟
✅70. 爬楼梯 🌟
✅746. 使用最小花费爬楼梯 🌟
✅115. 不同的子序列 🌟🌟🌟
✅139. 单词拆分 🌟🌟
✅140. 单词拆分 II 🌟🌟🌟
✅1262. 可被三整除的最大和 🌟🌟
✅2746. 字符串连接删减字母 记忆化搜索 单词的开头和结尾 🌟🌟
✅1186. 删除一次得到子数组最大和 最大子数组和+删除一个元素 🌟🌟
✅486. 预测赢家 dp[i][j]表示从i到j当前玩家与另一玩家分数差的最大值 🌟🌟
✅787. K 站中转内最便宜的航班 dijkstra、DP 🌟🌟
✅10. 正则表达式匹配 记忆化搜索+递归：分情况讨论 🌟🌟🌟
✅887. 鸡蛋掉落 二分代替线性搜索，minMax 🌟🌟🌟
✅312. 戳气球 dp[i][j]表示nums[i:j]开区间获得硬币的最大数量，枚举最后被戳破的气球 🌟🌟🌟

背包问题

变体：

  • 0/1背包问题（0/1 Knapsack Problem）：在给定的一组物品中，每个物品要么全部选取，要么不选取。每个物品只能选择一次放入背包中。
  • 完全背包问题（Unbounded Knapsack Problem）：在给定的一组物品中，每个物品的数量是无限的，可以重复选择放入背包中。每个物品可以选择多次放入背包中。
  • 多重背包问题（Multiple Knapsack Problem）：在给定的一组物品中，每个物品有一个限制数量。每个物品可以选择多次放入背包中，但是放入的数量不能超过其限制数量。
  • 分组背包问题（Group Knapsack Problem）：将物品分为若干组，每组中的物品只能选择一个放入背包中。每个物品只能选择一次放入背包中。
  • 有限背包问题（Bounded Knapsack Problem）：在给定的一组物品中，每个物品有一个限制数量。每个物品只能选择一次放入背包中，且放入的数量不能超过其限制数量。
  • 带价值上限的背包问题（Knapsack Problem with Value Limit）：在给定的一组物品中，每个物品有一个限制数量和一个价值上限。每个物品只能选择一次放入背包中，且放入的数量和总价值不能超过其限制。

0/1背包问题和完全背包问题是经典的NP问题。在求解背包问题时，需要遍历所有可能的物品组合来寻找最优解，而这个过程的时间复杂度通常是指数级的。因此，背包问题属于一类需要指数级时间复杂度的问题，即NP问题。

NP（Non-deterministic Polynomial time）是一个计算复杂性理论中的重要概念，它是指“非确定多项式时间”。一个问题属于NP，意味着对于该问题的一个解，可以在多项式时间内进行验证。然而，与确定性算法不同，NP问题目前没有已知的高效算法可以在多项式时间内找到解。
一个经典的NP问题是旅行商问题（Traveling Salesman Problem，TSP），即寻找最短的路径，使得一个旅行商可以依次访问一系列城市并返回起始城市，而且每个城市只能访问一次。
另一个重要的概念是NP完全性（NP-completeness），它指的是一类NP问题，被认为是计算上最难的问题之一。如果一个问题是NP完全的，那么它在多项式时间内可归约为任何其他的NP问题。
虽然目前尚未找到多项式时间的算法来解决所有的NP问题，但在实际应用中，我们可以采用启发式算法、近似算法和优化技巧等方法来求解NP问题的近似解或者找到满足特定要求的解。

算法框架

0/1背包：给定一个背包的容量C和n个物品，每个物品有两个属性：重量w和价值v。在限定的背包容量下选择物品，使得放入背包的物品总价值最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def knapsack_01(weights, values, capacity):
    n = len(weights)

    # dp[i][j]表示在前i个物品中选择物品放入容量为j的背包中的最大价值。
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # base case: dp[0][j] = 0（表示没有物品可选时的最大价值为0）; dp[i][0] = 0（表示容量为0时无法放入任何物品，所以最大价值为0）

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

    selected_items = []
    j = capacity
    for i in range(n, 0, -1):
        if dp[i][j] != dp[i - 1][j]:
            selected_items.append(i - 1)
            j -= weights[i - 1]

    return dp[n][capacity], selected_items[::-1]


# 示例用法
weights = [2, 3, 4, 5]  # 物品的重量
values = [3, 4, 5, 6]  # 物品的价值
capacity = 8  # 背包的容量

max_value, selected_items = knapsack_01(weights, values, capacity)
print("最大价值:", max_value)
print("选中的物品索引:", selected_items)

完全背包：给定一个背包的容量C和n个物品，每个物品有两个属性：重量w和价值v。在容量有限的背包中，可以选择任意数量的物品放入背包中，使得物品的总重量不超过背包容量，并且总价值最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def knapsack_unbounded(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(1, capacity + 1):
        for j in range(n):
            if weights[j] <= i:
                dp[i] = max(dp[i], dp[i - weights[j]] + values[j])

    return dp[capacity]


# 示例用法
weights = [2, 3, 4, 5]  # 物品的重量
values = [3, 4, 5, 6]  # 物品的价值
capacity = 8  # 背包的容量

max_value = knapsack_unbounded(weights, values, capacity)
print("最大价值:", max_value)

力扣指南

动态规划——背包
题目 技巧 难度
✅416. 分割等和子集 【01背包】注意逻辑 🌟🌟
✅518. 零钱兑换 II 【完全背包】好难 🌟🌟
✅494. 目标和 【01背包】 🌟🌟
✅474. 一和零 【01背包】 🌟🌟
✅279. 完全平方数 【完全背包】 🌟🌟
❌879. 盈利计划 【01背包】 🌟🌟
❌1049. 最后一块石头的重量 II 【01背包】 🌟🌟
❌1230. 抛掷硬币 【01背包】 🌟🌟
❌1449. 数位成本和为目标值的最大数字 【完全背包】 🌟🌟
❌322. 【完全背包】 🌟🌟