Kmoon Blog

【算法合集】：动态规划

约 2.8k 字 6 min

动态规划

首先确定有哪些状态，初始化 dp 数组，初始化 dp 数组的时候需要考虑纬度、状态。

当前状态来源于前面的状态，写状态转移方程的时候，思考 = 号左边的状态在右边有哪些来源（依赖前面哪些状态）。

线性 DP

最基础的一维 DP，dp [i] 只依赖前面 dp [i-1] / dp [i-2]

状态：dp[i] = 前 i 位置最优解

经典题：

  1. 打家劫舍 Ⅰ、Ⅱ

偷当前房子依赖于偷没偷左边的房子，如果偷了左边的就不能偷当前的,保持原来的状态：dp[i-1]，如果没偷左边的当前房子就可以偷：dp[i-2] + nums[i]，两者取最大值即可。

打家劫舍 Ⅱ 数据结构变成了环形数组，首尾相互挨着，只能选择偷一个，所以我们分别去掉首尾计算一次，取最大值即可。

  1. 爬楼梯、最小花费爬楼梯
  • 爬楼梯这里考虑爬上当前台阶来源于两种方法：1️⃣ 从前两个台阶爬上来 2️⃣ 从前一个台阶爬上来，所以很容易推出状态转移方程：dp[i] = dp[i-2] + dp[i-1]，这里可以看出爬楼梯本质上就是斐波那契数列
  • 最小花费爬楼梯加了一个新条件，目标从“计数”变成“求最值”:dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])，需要考虑成本取最小值。
  1. 斐波那契数、杨辉三角
  • 斐波那契数题目已经给出了状态转移方程：dp[n] = dp[n-1] + dp[n-2]
  • 杨辉三角同样也是给出了状态转移过程：每个数来源于左上方 + 右上方的值，即上一行的两个值，需要一行一行算出当前行的值。
  1. 比特位计数

需要统计二进制表示中 1 的个数，这里我们知道二进制是逐个进位的，后面的数来源于前面的数(i 的状态依赖于 i 整除 2 的状态)。比如 3（11）的二进制中 1 的个数 = 1（01）的二进制中 1 的个数 + 3（11）原本末尾一位 1 的个数。

总结来看就是：dp[i] = dp[i // 2] + (i & 1)，这里整除 2 其实也就是右移一位（dp[i] » 1），(i & 1) 就是看 i 末尾是不是 “1”。

区间 DP

左右区间 i ~ j

dp [i][j]：区间 [i,j] 的答案，从小区间推大区间

枚举区间长度 → 枚举起点 i，终点 j=i+len-1

经典题：

  1. 最大子数组和

从小区间推大区间，数组里面有负数，要么拼到后面，要么重新开始，两者取最大值：dp[i] = max(dp[i - 1] + nums[i], nums[i])，返回的时候取最大：return max(dp)

  1. 最长递增子序列

外层枚举每一个位置 i（作为子序列的结尾），内层枚举 i 前面所有位置 j（尝试将 i 接在 j 后面），能递增：nums[j] < nums[i]，说明可以把 nums[i] 接在以 j 结尾的序列后面

  1. 乘积最大子数组

这道题同样存在负数，计算乘法可能会对结果产生反转。需要维护两个dp数组，一个乘积最大值，一个乘积最小值。乘积最大值的3个来源：拼在后面、重新开始、最小值拼，乘积最小值的3个来源：拼在后面、重新开始、最大值拼，最后结果肯定是返回乘积最大值数组的最大值

  1. 回文子串、最长回文子串

因为要判断回文子串，需要先枚举子串长度，再枚举当前长度下所有可能的起始位置，状态转移就是只要首尾两个字符相等就可以更新，因为题目求总数，所以需要统计一下

最长回文子串求的是最长子串，只需要维护一个最长长度即可

坐标/网格/棋盘 DP

从左上走到右下，只能右 / 下；dp [i][j] 由上边 / 左边转移

经典题：

  1. 不同路径 Ⅰ、Ⅱ
  1. 最小路径和
  1. 最大正方形

模板：dp[i][j]=dp[i-1][j]+dp[i][j-1] / min(…)

二维 DP / 双串 DP

二维 DP

二维 DP 是指存在另一个纬度的状态，比如买卖股票场景下就存在持股、不持股两种状态。

  1. 买卖股票的最佳时机、买卖股票的最佳时机含冷冻期

双串

双串 DP 是指需要在两个数据结构上（数组、字符串）考虑。

  1. 最长公共子序列

  2. 编辑距离

树形 DP

DFS + DP

  1. 打家劫舍 Ⅲ
  1. 不同的二叉搜索树

背包问题

背包问题需要理清 3 个核心顺序：

1. 先物品 还是 先容量

只需要分析题目是“组合”还是“排列”场景即可

因为组合问题不考虑顺序，1+2 和 2+1 算同一种。

先物品 = 控制物品只能按固定顺序出现，不会回头选，不产生新顺序 → 组合

外层物品 = 单向遍历，不回头，物品只能按顺序出现，后面的物品不能再和前面的组合 → 无顺序 = 组合

例如：零钱兑换、零钱兑换 II、完全平方数、分割等和子集、目标和

for 物品 in 物品:
    for 容量 in range(物品, 总容量+1):

因为排列问题中顺序不同，算不同的答案。1+2 和 2+1 算两种

先容量 = 每个位置都能选所有物品，会回头选，产生新顺序 → 排列

外层容量 = 每个位置都能选全部物品，每个容量位置，都可以重新选所有物品 → 有顺序 = 排列

例如：单词拆分、组合总和 IV

for 容量 in range(总容量+1):
    for 物品 in 物品:

2. 容量正序 还是 倒序

决定是 01 背包 还是 完全背包

每个物品只能用一次，所以不能让后面的更新用到前面刚更新的值 → 必须倒序

物品可以用无限次，希望后面能用到前面刚更新的值 → 必须正序

3. 初始化顺序：求最小 / 求方案数 / 求可达

决定 dp 数组怎么初始化

dp[0] = 0，其余 = 无穷大

dp[0] = 1，其余 = 0

dp[0] = True，其余 = False

01 背包

  1. 分割等和子集

  2. 目标和

完全背包

  1. 完全平方数

  2. 零钱兑换

  3. 单词拆分

核心思想 动态规划 = 把大问题拆成小问题，并把小问题答案记下来。 checklist 对任意一道题，能在草稿纸上 30 秒写出：

  1. dp 定义（dp 表示什么？）
  2. 状态转移（最后一步从哪来？）
  3. 初始值（初始值是什么？）
  4. 遍历顺序（按什么顺序算？） 7种状态定义模板
  1. 简单递推型：当前答案由前面几个答案推出 当前怎么来，就看最后一步/上一层。
  2. 线性选择型：当前位置选 or 不选 到当前位置时，要么接上前面，要么自己重新开始 / 选或不选。
  3. 状态机 DP：每天有几种状态 每天不是一个数，而是几种状态。
  4. 网格 DP：到这个格子怎么来 看到网格，先想：从上来？从左来？
  5. 树形 DP：选当前节点 or 不选当前节点 树上题，经常是“选我”还是“不选我”。
  6. 区间 / 回文 DP：看区间 [i, j] 回文看两头：两头相等，里面也得是回文。
  7. 双序列 DP：两个字符串一起看 看到两个字符串，先定义：前 i 个 和 前 j 个。
  8. 背包 DP：选或不选，能不能凑出来 / 有多少种 / 最少几个 背包只分 3 问：
  9. 能不能凑出来？
  10. 有多少种凑法？
  11. 最少/最多用多少？
  12. 组合计数型：枚举“最后的结构” 不是枚举答案，而是枚举“根”。

面试思路

  1. 是一条线吗？
  1. 是网格吗？
  1. 是两个字符串吗？
  1. 是回文吗？
  1. 是“凑和”吗？
  1. 是树吗？
  1. 是股票吗？

#Algorithms