动态规划

动态规划（Dynamic Programming, 简称 DP）是计算机科学中一种重要的算法设计思想，常用于解决具有 重叠子问题 和 最优子结构 性质的问题。以下是动态规划相关的知识点总结：

动态规划的核心思想

  1. 重叠子问题
    • 问题可以被分解为子问题，子问题之间有重复计算。
    • 示例：斐波那契数列，F(n) = F(n-1) + F(n-2)，需要重复计算子问题。
  2. 最优子结构
    • 一个问题的最优解可以由其子问题的最优解组合得到。
    • 示例：最短路径问题，某个节点的最短路径由其前驱节点的最短路径加上路径长度决定。
  3. 状态转移方程
    • 明确当前状态与之前状态之间的关系。
    • 示例：dp[i] = dp[i-1] + dp[i-2]（斐波那契数列）。

动态规划的分类

1. 按解题顺序分类

  1. 自顶向下（记忆化搜索）
    • 通过递归实现，配合缓存避免重复计算。
    • 示例：斐波那契数列递归实现，使用数组存储中间结果。
  2. 自底向上（迭代）
    • 从最小子问题开始计算，逐步推导出原问题的解。
    • 示例：斐波那契数列用循环计算。

2. 按问题类型分类

  1. 线性动态规划
    • 问题有线性结构，例如：最长递增子序列、斐波那契数列。
    • 示例状态转移方程：dp[i] = max(dp[j]) + 1（最长递增子序列）。
  2. 区间动态规划
    • 问题涉及数组的某个子区间，例如：矩阵链乘、回文子串分割。
    • 示例状态转移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost)。
  3. 背包问题（0-1 背包、多重背包、完全背包）
    • 描述选择物品以最大化价值的问题。
    • 示例状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value)。
  4. 二维动态规划
    • 通常应用在棋盘类问题，例如：最长公共子序列、编辑距离。
    • 示例状态转移方程：dp[i][j] = dp[i-1][j-1] + 1（最长公共子序列）。
  5. 树形动态规划
    • 问题在树结构上，例如：树的直径、树的分割。
    • 示例状态转移方程：dp[u] = max(dp[v] + weight)。
  6. 状态压缩动态规划
    • 通过位运算优化状态空间，例如：旅行商问题（TSP）、子集问题。
    • 示例状态转移方程：dp[S][i] = min(dp[S'][j] + cost)。
  7. 博弈型动态规划
    • 描述两人轮流操作的博弈问题，例如：石子游戏、取硬币问题。
    • 示例状态转移方程：dp[i][j] = max(pick_left, pick_right)。

动态规划的解题步骤

  1. 定义状态（State）
    • 用一个或多个变量描述问题的状态。
    • 示例：dp[i] 表示前 i 个元素的最优解。
  2. 状态转移方程（State Transition Formula）
    • 明确如何从一个状态转移到另一个状态。
    • 示例：dp[i] = dp[i-1] + dp[i-2]。
  3. 初始化（Initialization）
    • 明确初始条件。
    • 示例：dp[0] = 1, dp[1] = 1。
  4. 计算顺序（Order of Calculation）
    • 明确计算状态的顺序，从小问题到大问题。
    • 示例：从 i=2 到 n。
  5. 返回结果（Result Extraction）
    • 根据问题需要提取结果。
    • 示例：返回 dp[n]。

动态规划的常见问题与技巧

  1. 数组压缩优化空间
    • 仅使用 O(k) 或 O(1) 空间存储状态。
    • 示例：斐波那契数列只需两个变量存储当前状态。
  2. 滚动数组技巧
    • 用有限的数组存储状态，按需覆盖。
    • 示例：背包问题用一维数组代替二维数组。
  3. 状态优化
    • 利用问题的特殊性质减少状态数。
    • 示例：完全背包问题可以优化为一维数组。
  4. 决策单调性
    • 某些问题状态转移时，决策具有单调性。
    • 示例：滑动窗口优化最优值。

经典动态规划问题

  1. 基础问题
    • 斐波那契数列（Fibonacci）
    • 爬楼梯问题（Climbing Stairs）
    • 打家劫舍问题（House Robber）
  2. 字符串问题
    • 最长公共子序列（LCS）
    • 编辑距离（Edit Distance）
    • 最长回文子串（Longest Palindromic Substring）
  3. 背包问题
    • 0-1 背包
    • 完全背包
    • 多重背包
  4. 路径问题
    • 最小路径和（Minimum Path Sum）
    • 不同路径（Unique Paths）
    • 矩阵路径问题
  5. 区间问题
    • 戳气球问题
    • 石子合并问题
  6. 高级问题
    • 旅行商问题（TSP）
    • 股票买卖问题
    • 棋盘覆盖问题