动态规划
动态规划
动态规划(Dynamic Programming, 简称 DP)是计算机科学中一种重要的算法设计思想,常用于解决具有 重叠子问题 和 最优子结构 性质的问题。以下是动态规划相关的知识点总结:
动态规划的核心思想
- 重叠子问题
- 问题可以被分解为子问题,子问题之间有重复计算。
- 示例:斐波那契数列,
F(n) = F(n-1) + F(n-2)
,需要重复计算子问题。
- 最优子结构
- 一个问题的最优解可以由其子问题的最优解组合得到。
- 示例:最短路径问题,某个节点的最短路径由其前驱节点的最短路径加上路径长度决定。
- 状态转移方程
- 明确当前状态与之前状态之间的关系。
- 示例:
dp[i] = dp[i-1] + dp[i-2]
(斐波那契数列)。
动态规划的分类
1. 按解题顺序分类
- 自顶向下(记忆化搜索)
- 通过递归实现,配合缓存避免重复计算。
- 示例:斐波那契数列递归实现,使用数组存储中间结果。
- 自底向上(迭代)
- 从最小子问题开始计算,逐步推导出原问题的解。
- 示例:斐波那契数列用循环计算。
2. 按问题类型分类
- 线性动态规划
- 问题有线性结构,例如:最长递增子序列、斐波那契数列。
- 示例状态转移方程:
dp[i] = max(dp[j]) + 1
(最长递增子序列)。
- 区间动态规划
- 问题涉及数组的某个子区间,例如:矩阵链乘、回文子串分割。
- 示例状态转移方程:
dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost)
。
- 背包问题(0-1 背包、多重背包、完全背包)
- 描述选择物品以最大化价值的问题。
- 示例状态转移方程:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value)
。
- 二维动态规划
- 通常应用在棋盘类问题,例如:最长公共子序列、编辑距离。
- 示例状态转移方程:
dp[i][j] = dp[i-1][j-1] + 1
(最长公共子序列)。
- 树形动态规划
- 问题在树结构上,例如:树的直径、树的分割。
- 示例状态转移方程:
dp[u] = max(dp[v] + weight)
。
- 状态压缩动态规划
- 通过位运算优化状态空间,例如:旅行商问题(TSP)、子集问题。
- 示例状态转移方程:
dp[S][i] = min(dp[S'][j] + cost)
。
- 博弈型动态规划
- 描述两人轮流操作的博弈问题,例如:石子游戏、取硬币问题。
- 示例状态转移方程:
dp[i][j] = max(pick_left, pick_right)
。
动态规划的解题步骤
- 定义状态(State)
- 用一个或多个变量描述问题的状态。
- 示例:
dp[i]
表示前i
个元素的最优解。
- 状态转移方程(State Transition Formula)
- 明确如何从一个状态转移到另一个状态。
- 示例:
dp[i] = dp[i-1] + dp[i-2]
。
- 初始化(Initialization)
- 明确初始条件。
- 示例:
dp[0] = 1, dp[1] = 1
。
- 计算顺序(Order of Calculation)
- 明确计算状态的顺序,从小问题到大问题。
- 示例:从
i=2
到n
。
- 返回结果(Result Extraction)
- 根据问题需要提取结果。
- 示例:返回
dp[n]
。
动态规划的常见问题与技巧
- 数组压缩优化空间
- 仅使用
O(k)
或O(1)
空间存储状态。 - 示例:斐波那契数列只需两个变量存储当前状态。
- 仅使用
- 滚动数组技巧
- 用有限的数组存储状态,按需覆盖。
- 示例:背包问题用一维数组代替二维数组。
- 状态优化
- 利用问题的特殊性质减少状态数。
- 示例:完全背包问题可以优化为一维数组。
- 决策单调性
- 某些问题状态转移时,决策具有单调性。
- 示例:滑动窗口优化最优值。
经典动态规划问题
- 基础问题
- 斐波那契数列(Fibonacci)
- 爬楼梯问题(Climbing Stairs)
- 打家劫舍问题(House Robber)
- 字符串问题
- 最长公共子序列(LCS)
- 编辑距离(Edit Distance)
- 最长回文子串(Longest Palindromic Substring)
- 背包问题
- 0-1 背包
- 完全背包
- 多重背包
- 路径问题
- 最小路径和(Minimum Path Sum)
- 不同路径(Unique Paths)
- 矩阵路径问题
- 区间问题
- 戳气球问题
- 石子合并问题
- 高级问题
- 旅行商问题(TSP)
- 股票买卖问题
- 棋盘覆盖问题
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 寻觅~流光!
评论