动态规划问题总结

基本原理

动态规划核心是穷举求最值，动态规划三要素：

  1. 最优子结构：是否 —— 能够通过子问题的最值得到原问题的最值。
    • 子问题间必须互相独立，不能有制约关系。
  2. 状态转移方程：如何 —— 通过子问题的最值得到原问题的最值。也就是暴力解。
  3. 重叠子问题：使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

简而言之，如果一个问题要求最值，而且可以分解成子问题，就可以尝试写状态转移方程，写出来就可以看出来有没有重叠子结构了（递归树中有没有重复的节点），就可以再考虑是否可以动态规划解决。

如何分析一个动态规划问题？

  1. 明确「Base Case」：最简单的情况，基本情况。
  2. 明确「状态」：原问题和子问题中变化的量。
  3. 明确「选择」：可以导致状态产生改变的行为。
  4. 明确「dp 数组/函数」的含义：参数/索引一般是状态，返回值是要求的值。但是有时要灵活变通使得通项公式好写。几个可以考虑的方向：
    • 在暴力求解中路径到以该状态为止的情况的最值。
  5. 写状态转移方程，经常不止会用到前一个状态，而是会用到所有过去的状态。

注：dp数组的本质是cache,有时候index不是连续的（与所给input的值而非数量有关），这时候需要考虑用hashing来存储中间结果。

# 自顶向下递归的动态规划
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数组一般有两种类型：

  1. 一维数组：
    • 子数组arr[0..i]中，我们要求的值是dp[i]。
    • 子数组arr[0..i]中，以arr[i]状态结尾的情况的最值是dp[i]。
  2. 二维数组：
    • 一般是涉及两个数组，或者两个字符串的：在子数组 arr1[0..i] 和子数组 arr2[0..j] 中，我们要求的子序列长度为dp[i][j]：经典案例：Edit Distance
    • 在子数组 array[i..j] 中，我们要求的子序列的长度为 dp[i][j]。

背包问题

· 面试笔记