木易

# Road Map

刷题路线：

  • 最经典单串：300
  • 最经典双串：1143
  • 经典问题：
  1. 三角形最小路径和
  2. 最大子序和
  3. 乘积最大子数组
  4. 鸡蛋掉落（DP+二分）
  5. 俄罗斯套娃信封问题
  • 打家劫舍系列: (打家劫舍 3 是树形 DP)
  1. 打家劫舍
  2. 打家劫舍 II
  • 股票系列:
  1. 买卖股票的最佳时机
  2. 买卖股票的最佳时机 II
  3. 买卖股票的最佳时机 III
  4. 买卖股票的最佳时机 IV
  5. 最佳买卖股票时机含冷冻期
  6. 买卖股票的最佳时机含手续费
  • 字符串匹配系列
  1. 编辑距离
  2. 通配符匹配
  3. 正则表达式匹配

# 线性 dp

线性 dp 的模型是线性的

# 问题分类

线性 dp 可以按分析方式分为几类：

  • 坐标型
  • 序列型
  • 划分型

# 坐标型

坐标型 dp 一般可以分为一维坐标和二维坐标

  • 坐标记录状态

  • 可以用滚动数组进行空间优化

# 一维坐标

硬币组合: 足够的 2，5，7 面值的硬币，问最少用多少个硬币能组合出面值 27（有多少种方式凑出面值 27）

f(i)f(i) 表示凑出 i 元所有的最少硬币数（凑出 i 元的方案数）

# 518. 零钱兑换 II (opens new window)

# 剑指 Offer 46. 把数字翻译成字符串 (opens new window)

# 二维坐标

不同路径：在一个二维棋盘中，机器人从左上角走到右下角，有多少种走法

# 62. 不同路径 (opens new window)

# 63. 不同路径 II (opens new window)

# 64. 最小路径和 (opens new window)

# 120. 三角形最小路径和 (opens new window)

# 炸弹袭击 (opens new window)

二维矩阵中的格子为空，敌人，墙，炸弹可以放在任意空地上，炸弹会杀死同一行和同一列没有墙阻隔的敌人；问一个炸弹杀死的最大敌人数

算法思路：

  • 记录dp[i][j][0,1,2,3]dp[i][j][0,1,2,3]分别为向四个方向能炸死的敌人数目
  • 从四个方向，做差分，记录每个位置在此方向上能够炸死的敌人数目
  • 四个方向求和，迭代得最大值

# 序列型

序列型一般分为单序列、双序列

  • 一般需要自定义空序列表示 f[0]

  • 有时候会有 K 维序列，表示 K 种状态

# 划分型

划分型是将序列分成若干段，每一段具有最大/最小的性质）

给定长度为 N 的序列，要求划分为若干段

  • 段数不限，或指定 K 段

  • 每一段满足一定的性质（最小代价，能不能等） 做法：

  • 类似于序列型动态规划，但是通常要加上段数信息

  • 一般用f[i+1][k]f[i + 1][k]来记录前 i 个元素（元素0=>i−1,f[0][k]0=>i-1,f[0][k]表示空序列）分成 k 段的性质，如最小代价

← 0x52_背包dp →