力扣总结常见算法（七）：动态规划

Ian

2021-02-01 约 1178 字预计阅读 3 分钟次阅读

动态规划是一种特殊的递归，适用于有重叠子问题的场景。

存在大量重叠的子问题时，普通的递归写法会重复计算这些子问题，浪费大量时间。动态规划会保存所有子问题的结果，避免重复计算。

动态规划也有递归和非递归两种形式。递归形式的动态规划也叫记忆化递归，非递归形式即是保存中间结果的递推。

python 在递归函数上加一个 @lru_cache(None) 的装饰器即可实现记忆化递归。非递归形式一般初始化一个 k（动态参数个数）维的数组保存子问题的结果。

递归层数太多时容易爆栈，用非递归形式更好。但有时所求问题只会用到稀疏的子问题，此时用递归形式更节省时间。

1 单推 dp

有的问题结果完全依赖于几个初始值和递推式：

有时能用简洁的函数表达式直接表达，比如组合数
有的递推式可以用矩阵快速幂优化时间

1.1 基础

0062 不同路径
0070 爬楼梯
0096 不同的二叉搜索树
0279 完全平方数
0397 整数替换
0509 斐波那契数

1.2 进阶

0338 比特位计数
0343 整数拆分
0790 多米诺和托米诺平铺

1.3 挑战

0552 学生出勤记录 II

2 线性 dp

2.1 基础

0091 解码方法
0322 零钱兑换
0377 组合总和 Ⅳ

2.2 进阶

0032 最长有效括号
0042 接雨水
0131 分割回文串
0403 青蛙过河
0639 解码方法 II
0801 使序列递增的最小交换次数
0823 带因子的二叉树

2.3 挑战

0005 最长回文子串
0135 分发糖果
0264 丑数 II

3 线性 dp 典型问题

3.1 子数组/子串

0053 最大子序和
0152 乘积最大子数组
0413 等差数列划分
0467 环绕字符串中唯一的子字符串
0689 三个无重叠子数组的最大和

3.2 子序列

0300 最长递增子序列
0354 俄罗斯套娃信封问题
0368 最大整除子集
0376 摆动序列
0673 最长递增子序列的个数

3.3 多串 dp

0044 通配符匹配
0097 交错字符串
0115 不同的子序列
0583 两个字符串的删除操作
0712 两个字符串的最小ASCII删除和

3.4 打家劫舍系列

0198 打家劫舍
0213 打家劫舍 II
0740 删除与获得点数

3.5 股票系列

0121 买卖股票的最佳时机
0122 买卖股票的最佳时机 II
0123 买卖股票的最佳时机 III
0188 买卖股票的最佳时机 IV
0309 最佳买卖股票时机含冷冻期
0714 买卖股票的最佳时机含手续费

3.6 背包 dp

0474 一和零
0518 零钱兑换 II
0638 大礼包
0691 贴纸拼词

4 矩阵 dp

4.1 基础

0063 不同路径 II
0064 最小路径和
0120 三角形最小路径和

4.2 进阶

0329 矩阵中的最长递增路径
0576 出界的路径数
0688 骑士在棋盘上的概率
0764 最大加号标志

4.3 挑战

0174 地下城游戏
0221 最大正方形
0741 摘樱桃

5 区间 DP

5.1 基础

0005 最长回文子串
0516 最长回文子序列

5.2 进阶

0087 扰乱字符串
0664 奇怪的打印机

5.3 挑战

0312 戳气球
0375 猜数字大小 II
0546 移除盒子
0730 统计不同回文子序列

6 哈希 dp

有时需要递推的不是单纯的值，而是集合/计数器

6.1 基础

0416 分割等和子集
0494 目标和

6.2 进阶

0241 为运算表达式设计优先级

6.3 挑战

0446 等差数列划分 II - 子序列

7 状压 dp

0416 分割等和子集
0473 火柴拼正方形
0526 优美的排列
0698 划分为k个相等的子集
0805 数组的均值分割

8 数位 dp

0233 数字 1 的个数
0600 不含连续1的非负整数
0788 旋转数字

9 图上 dp

0126 单词接龙 II

10 博弈 dp

0464 我能赢吗
0486 预测赢家

11 dp 优化

11.1 dp+上下界

0808 分汤

11.2 dp+前缀和

0629 K个逆序对数组
0813 最大平均值和的分组

11.3 dp+二分

0514 自由之路

11.4 dp+构造

0264 丑数 II
0300 最长递增子序列
0313 超级丑数
0673 最长递增子序列的个数

11.4 dp+折半搜索

0805 数组的均值分割

目录

力扣总结 常见算法（七）：动态规划