常见dp问题的状态表示
目录
前言
一、动态规划核心五步
二、常见 dp 问题的状态表示
1.斐波那契数列模型
2.路径问题
3.简单多状态 dp 问题
4.子数组问题
5.子串问题
6.子序列问题
7.回文串问题
8.两个数组的 dp 问题
9. 01 背包问题
10. 完全背包问题
11. 二维费用 01 背包问题
12. 排列问题
总结
前言
解决 dp 问题的关键首先是确定状态表示，确定正确的状态表示，才能结合题目要求顺利推导出状态转移方程。但状态表示往往是根据经验定义的，下面介绍常见类型题目的状态表示。
一、动态规划核心五步
1. 确定状态表示 - 根据 题目要求，结合经验(往往定义以 i,j 位置为结尾/开始......)，有时也根据发现重复子问题 确定状态表示；
2. 推导状态转移方程: 即 dp[i] = ?
用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题），通常是分类讨论最后一个位置的各种情况，推导 dp[i] 和 dp[i - 1] 或者 dp[i + 1] 之间的关系；
3. 初始化：目的是保证填表时不越界，结合多开数组的技巧；
4. 确定填表顺序：填写当前状态值的时候，确保所需状态的值已经计算过了；
5. 返回值：结合题目要求 + 状态表示。
二、常见 dp 问题的状态表示
1.斐波那契数列模型
dp[i] 通常用来表示以第 i 个位置为结尾，研究 dp[i - 1], dp[i - 2], dp[i - 3]...等位置的状态和 dp[i] 之间的关系。
dp[i] 也可以表示以 i 位置为开始，研究 dp[i + 1], dp[i + 2], dp[i + 3]...等位置的状态和 dp[i] 之间的关系。
dp[i] 也可以表示以 i 位置为结尾，结合题目要求分类讨论 i 的各种情况，推导 dp[i] 和 dp[i - 1] 或者 dp[i + 1] 的关系。
2.路径问题
dp[i][j] 通常用来表示以 [i, j] 位置为结尾，结合题目要求分类讨论 [i, j] 的各种情况，推导 dp[i][j] 与 dp[i - 1, j], dp[i, j - 1] 或者 dp[i - 1, j - 1] 位置状态的关系。
dp[i][j] 通常用来表示以 [i, j] 位置为起始，结合题目要求分类讨论 [i, j] 的各种情况，推导 dp[i][j] 与 dp[i + 1, j], dp[i, j + 1] 或者 dp[i + 1, j + 1] 位置状态的关系。
3.简单多状态 dp 问题
dp[i] 表示以 i 位置为结尾，结合题目要求分类讨论 i 位置的情况，推导 dp[i] 与 dp[i - 1]之间的关系。
定义多个状态：f[i] 表示状态 1， g[i] 表示状态 2，分情况讨论 i 位置(例如选 i 位置元素，不选 i 位置元素等)，推导 f[i] 和 g[i] 与 f[i - 1] 和 g[i - 1] 之间的关系。
dp[i] 表示 i 位置为结尾，结合题目要求，发现题目存在多个状态，并且多个状态之间可以互相转移，那么可以通过状态机图进行表示：
根据状态机图的数量定义多个状态（通常是一个数组，类似二维 dp），再通过状态的转移条件推导 dp[i][0], dp[i][1], dp[i][2] 同 dp[i - 1][0], dp[i - 1][1], dp[i - 1][2] 之间的关系。
4.子数组问题
dp[i] 表示以 i 位置为结尾的子数组，为两种情况：要么前面元素结合 i 位置元素，要么只有 i 位置元素，推导 dp[i] 和 dp[i - 1], i 位置元素之间的关系 。
子数组问题中可能也会出现多状态 dp 问题：
例如：环形数组子数组最大和问题，需要分别求最大和最小和；数组最大乘积，因为数组元素有正有负，需要分别求最大积和最小积，因此需要定义多状态，根据 i 位置的元素分类讨论，推导 f[i], g[i] 同 f[i - 1], g[i - 1] 之间的关系。
例如：等差数列或者斐波那契数列等，i 位置元素还需要结合 i - 1， i - 2 位置的元素分情况讨论 dp[i] 和 dp[i - 1] 的关系。
5.子串问题
dp[i] 表示以 i 位置为结尾的子串，结合题目要求，分类讨论 i 位置字符情况，甚至有可能需要定义 j(0 <= j <= i),讨论 [j, i] 区间内单词的情况，推导 dp[i] 和 dp[j - 1] 之间的关系。
6.子序列问题
dp[i] 表示以 i 位置为结尾的子序列，定义 j (0 <= j <= i)，结合题录要求分析 i 位置元素情况，或 [j, i] 区间的子串情况，推导 dp[i] 和 dp[j] 之间的关系，这里往往需要取最大值/最小值，因为有多个 dp[j]。
同样，这里也可能会出现多状态：
例如：摆动数组问题，需要定义以 i 为结尾上升状态的子序列，及下降的子序列，求出最长摆动序列的长度。
例如：最长子序列的个数，还需要一个状态表示最长子序列的个数。
dp[i][j] 通常用来表示以 i 和 j 位置元素为结尾的子序列，用于求等差序列或者斐波那契序列，因为只有一个元素无法确定等差序列和斐波那契序列，根据两个元素的公差/关系，能够推导出前一个元素，假设位置为 k ，通常会借用一个哈希表查询这个元素是否存在，推导 dp[i][j] 与 dp[k][i] 的关系。
7.回文串问题
isPal[i][j] 通常表示以 i 位置为开头，j 位置为结尾的子串是否为回文串，这个状态表示能够将所有的回文串都统计出来，非常关键。
回文串分析方法：主要根据回文串的性质，i 位置元素和 j 位置元素：
如果两元素相等，且i == j 或者 i + 1 == j，isPal[i][j] = true;
否则如果两元素仅相等：isPal[i][j] = isPal[i + 1][j - 1]。
再定义 dp[i] 表示以 i 位置为结尾的子串，再定义 j (0 <= j <= i),结合题目要求分析 [j, i] 区间的元素是否回文，推导 dp[i] 和 dp[j - 1] 的关系。
8.两个数组的 dp 问题
dp[i][j] 通常表示以 s1[0, i] 区间，s2[0, j] 区间，结合题目要求，分析 s1 i 位置元素和 s2 j 位置元素等情况（通常是是否相等），推导 dp[i][j] 和 dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] 之间的关系。
通配符问题：* 分为两种情况：匹配空字符 或 可以匹配多个字符，根据上述性质：
匹配空字符，推导 dp[i][j] 和 dp[i][j - 1] 的关系；
匹配多个字符，推导 dp[i][j] 和 dp[i - 1][j] 的关系。
子数组问题：dp[i][j] 不再表示 [0, i] 与 [0, j] 区间，而是表示 i 位置和 j 位置结尾的子数组；
两个数组 dp 问题：千万要看清题目是子数组还是子序列：
子数组就用 dp[i][j] 表示子数组；
子串就用 dp[i][j] [0, i], [0, j] 区间。
9. 01 背包问题
dp[i][j] 通常用来表示 [0, i] 区间内（体积/重量/和）不超过 j 的（最大价值/重量/和）。
dp[i][j] 通常用来表示 [0, i] 区间内（体积/重量/和）恰好等于 j 的（最大价值/重量/和）。
根据最后一个位置的情况讨论：
不选择 i 位置元素，找 dp[i][j] 和 dp[i - 1][j] 的关系；
选择 i 位置元素，找 dp[i][j] 和 dp[i - 1][j - nums[i]] 之间的关系；
10. 完全背包问题
dp[i][j] 通常用来表示 [0, i] 区间内（体积/重量/和）不超过 j 的（最大价值/重量/和）。
dp[i][j] 通常用来表示 [0, i] 区间内（体积/重量/和）恰好等于 j 的（最大价值/重量/和）。
根据最后一个位置的情况讨论：
不选择 i 位置元素，找 dp[i][j] 和 dp[i - 1][j] 的关系
选择 i 位置元素，找 dp[i][j] 和 dp[i][j - nums[i]] 之间的关系
11. 二维费用 01 背包问题
dp[i][j][k] 通常表示 [0, i] 区间内，体积不超过 j, 重量不超过 k 的能装下的最大价值。
和 01 背包问题完全相同，也是根据最后一个位置分情况讨论，假设 i 位置元素体积为 v, 重量为 w：
不选 i 位置元素： dp[i][j][k] = dp[i - 1][j][k]
选 i 位置元素：if(j >= v && k >= w) dp[i][j][k] = dp[i - 1][j - v][k - w]
12. 排列问题
背包问题解决的是组合问题，如果遇到排列问题，需要结合题目从重复子问题的角度定义 dp。
总结
以上是常见 dp 题型状态表示的定义方法。