动态规划(Dynamic Programming)

简称 DP , 是求解最优化问题的一种常用策略。

来自维基百科的解释：

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once,and storing their solutions.

  1. 将复杂的原问题拆解成若干个简单的子问题
  2. 每个子问题只解决一次，并保存它们的解
  3. 最后推导出原问题的解

可以用动态规划来解决的问题，通常具备2个特点

  1. 最有子结构（最优化原理）：通过求解子问题的最优解，可以获得原问题的最优解。
  2. 无后效行
    • 某阶段的状态一旦确定，则伺候过程的演变不再受此前各状态及决策的影响（未来与过去无关）
    • 在推倒后边阶段的状态时，只关心前面阶段的具体状态值，不关心这个状态怎么一步步推导出来的

动态规划的常规步骤：

  1. 定义状态（状态是原问题，子问题的解）比如定义dp[i]的含义

  2. 设置初始状态（边界） 比如设置dp[0]的值

  3. 确定状态转移方程 比如确定dp[i] 和 dp[i-1]的关系

通用的使用套路（一步步优化）

  • 暴力递归（自顶向下，出现了重复计算）
  • 记忆化搜索（自顶向下）
  • 递推（自底向下）

以下练习题整理转载自 力扣上的 DP 问题分类汇总

练习题

一，线性DP

最经典单串
300. 最长上升子序列
最经典双串

1143. 最长公共子序列

经典问题

120. 三角形最小路径和 53. 最大子序和 152. 乘积最大子数组 887. 鸡蛋掉落（DP+二分） 354. 俄罗斯套娃信封问题

322.零钱兑换

打家劫舍系列

198. 打家劫舍 213. 打家劫舍 II

股票系列

121. 买卖股票的最佳时机 122. 买卖股票的最佳时机 II

123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV

309. 最佳买卖股票时机含冷冻期 714. 买卖股票的最佳时机含手续费

字符串匹配系列

72. 编辑距离 44. 通配符匹配 10. 正则表达式匹配

二、区间 DP

516. 最长回文子序列 730. 统计不同回文子字符串 1039. 多边形三角剖分的最低得分 664. 奇怪的打印机 312. 戳气球

三、背包 DP

416. 分割等和子集 (01背包-要求恰好取到背包容量) 494. 目标和 (01背包-求方案数) 322. 零钱兑换 (完全背包)518. 零钱兑换 II (完全背包-求方案数) 474. 一和零 (二维费用背包)

五、树形 DP

124. 二叉树中的最大路径和 1245. 树的直径 (邻接表上的树形DP) 543. 二叉树的直径 333. 最大 BST 子树 337. 打家劫舍 III

五、状态压缩 DP

464. 我能赢吗 526. 优美的排列 935. 骑士拨号器 1349. 参加考试的最大学生数

六、数位 DP

233. 数字 1 的个数 902. 最大为 N 的数字组合 1015. 可被 K 整除的最小整数

七、计数型 DP

计数型DP都可以以组合数学的方法写出组合数，然后dp求组合数

62. 不同路径 63. 不同路径 II 96. 不同的二叉搜索树 (卡特兰数) 1259. 不相交的握手 (卢卡斯定理求大组合数模质数)

八、递推型 DP

所有线性递推关系都可以用矩阵快速幂做，可以O(logN)，最典型是斐波那契数列

70. 爬楼梯 509. 斐波那契数 935. 骑士拨号器 957. N 天后的牢房 1137. 第 N 个泰波那契数

九、概率型 DP

求概率，求数学期望 808. 分汤 837. 新21点

十、博弈型 DP

策梅洛定理，SG 定理，minimax

十一、记忆化搜索

本质是 dfs + 记忆化，用在状态的转移方向不确定的情况 329. 矩阵中的最长递增路径 576. 出界的路径数