• 状态就是把每一种方案、每一种情况进行压缩，只保留与限制、条件有关的部分，并分类存储，从而降低复杂度。
• 动态规划解题的关键点在于设置合适的状态，有了状态，转移往往会比较自然的给出。
• 状态的设置要求极简：
  • 可解性：我们所设的状态要在最后能够求出题目所求的基础上极力简化。
  • 可转移性：
    • 状态能够找到合适的转移。
    • 状态之间的转移有明确的顺序（即阶段），不能出现环。
    • 无后效性。

• 转移不能受状态之外的信息所影响。
• 即：状态A所代表的每一种方案转移到状态B所代表的每一种方案，转移系数、转移所选择的决策应当完全相同。
• 也即：影响转移的所有要素都已计入状态。
• 名字的来源？
• 解决方法：
  • 把影响转移的部分加到状态里。
  • 更改转移（费用提前计算dp）。
• 如果刚才那个题删掉第一维还能做吗？(注意与背包问题中的滚动数组区别开)
  • $f[j+1]=f[j]*(n-j)$

• 对于求解最优解的dp，我们不存方案数，而是存这类状态里最好的方案的答案，这就涉及到转移的另一个问题。
• 最优子结构：整体最优解至少可以由局部最优解转移而得到。
• 至少的含义是，整体最优解只要可以由局部最优解转移过来即可，也可以由非最优解转移过来。
• 解决方法：
  • 不止记录最优解，把某些特殊的解加到状态里。
  • 重新考虑状态。

• 给定一个表达式，让你添加括号，使结果最大。数字有负数，符号包含$+-\times$。表达式项数$\le 500$。
• 区间dp，设$f[i][j]$表示第$i$到$j$项加括号先算的答案，答案是$f[1][n]$。
• 考虑到因为有乘法、有负数，那么最大值可能由两个最小值相乘得到，所以另开一个数组记录最小值。

• 在代码实现动态规划的过程中，我们有两种常见的实现方法——刷表法和填表法。
• 两种方法各有利弊，要求全部掌握。

• 设由$\alpha$状态转移到$\beta$状态。
• 特点：枚举$\alpha$，计算$\alpha$对其他$\beta$的贡献。
• 举例：
  • $$\begin{cases}f[i+1][V] &= max(f[i+1][V],f[i][V]) \\ f[i+1][V+v[i]]&=max(\cdots,f[i][V]+w[i])\end{cases}$$
• 优点：
  • 正向转移，直观好写。
  • 可以只枚举合法（有值）的状态。（通过$hash$表等实现，在某些具有特殊性质的题目中可显著降低复杂度）
• 缺点：
  • 不能直观看到转移到某个状态的所有状态，不方便转移。
  • 对于某些动态规划不适用。

• 设由$\alpha$状态转移到$\beta$状态。
• 特点：枚举$\beta$，计算所有$\alpha$对$\beta$的贡献。
• 举例：$f[i][V]=max(f[i-1][V],f[i-1][V-v[i]]+w[i])$
• 优点：
  • 转移方程直观清晰，便于优化。
  • 适用范围更广泛。（很微小）
• 缺点：
  • 逆向转移，容易绕晕。
  • 在枚举之前不知道某个$\alpha$是否合法，不适用某些优化。

• 有一条大河，有$n$个地方有石子,第$i$个石子在$t_i$位置上，青蛙必须落在石子上，青蛙有两种跳法。
  • 跳$m_a$米，这种跳法最多跳$x_a$次，每次花费$c_a$体力。
  • 跳$m_b$米，这种跳法最多跳$x_b$次，每次花费$c_b$体力。
• 求跳到河对岸花费的最小体力。
• $c\le 10^3;n\le 10^4;m,t\le 10^9;x\le 10^3$

• 有n个物品，每个物品有自己的体积$a_i$。
• 有4个箱子，分别是$A$、$B$、$C$、$D$。
• 把每个物品放到一个箱子里，并给定$K_{1}-K_{4}$，要求：
  • $A+B \le K_1$
  • $C+D \le K_2$
  • $A+C \le K_3$
  • $B+D \le K_4$
• 求方案数
• $n \le 100; a_i,K \le 1000$

• 进行$n$圈赛车比赛，有$m$种轮胎，给定二维数组$MP[i][j]$表示第$i$种轮胎跑第$j$圈所需要的时间。
• 每进行完一圈，你可以选择换一个轮胎，换轮胎需要固定的时间$t$。
• 轮胎可以无限使用。
• 求最少多少时间能够完成比赛。
• $n,m \le 1000$

• 给定$n$个数，分成若干个集合。
• 每个集合的大小不小于$K$。
• 每个集合的价值是这个集合里的最大值与最小值之差。
• 一种划分的价值是每个集合的价值的最大值。
• 求出最小的划分价值。
• $1\le k \le n \le 3\times 10^5;1\le a_i\le 10^9$。

• 有一排$n$个电线杆，第$i$个的高度为$h_i$。
• 要在相邻的电线杆间造电线，给定常数C，每一根的代价是$|h_i-h_{i+1}|\times C$。
• 可以为电线杆增加高度，每个电线杆只能增加一次。为一根电线杆增加x高度的代价是$x^2$。
• 求最小化代价和。
• $n\le 5\times 10^4,C\le 100;h\le 10^9$

• 有$K$个任务，每个任务有自己的开始时间和持续时常
• 一共有$N$分钟，每分钟你都会进行决策。
  • 若你现在正在进行任务，则进入下一分钟。
  • 否则若当前有任务开始，那么必须做。
  • 如果有多个任务开始，则任选一个做。
• 求最大化不做任务的时间。
• $1\le N \le 10000; 1\le k \le 10000$。

• 在一个凹槽中放置了$n$层砖块、最上面的一层有$n$块砖，从上到下每层依次减少一块砖。
• 每块砖都有一个分值，敲掉这块砖就能得到相应的分值。
• 如果你想敲掉第$i$层的第$j$块砖的话，若$i=1$，你可以直接敲掉它；若$i>1$，则你必须先敲掉第$i-1$层的第$j$和第$j+1$块砖。
• 你现在可以敲掉最多$m$块砖，求得分最多能有多少。

• 序列问题放到树上，树上问题放到图（基环树、仙人掌、DAG）上。
• 任何序列问题放到树上都会使难度剧增，然而考虑树上问题在序列上的简化版往往是解决树上问题的出发点。
• 树型动规的特点：
  • 阶段：树上父子关系（大小子树关系）。
  • 状态：把序列问题放到树上不影响状态的设立（容易把序列问题放到树上）。
  • 转移：由儿子转移到父亲（由小子树转移到大子树）。
  • 具有明显的重叠子问题性质。

• 求树的直径
• 求树的重心
• 求树上最大独立集
• 求树上带权最大独立集
• $luogu\, 4438$
  • 给你一颗二叉树,每个叶子节点$i$有三个属性$a_i,b_i,c_i$
  • 每个非叶子节点都能标记往左右儿子的边中的一条边(分别记为$L$边和$R$边)
  • 设叶子节点$i$到根的路径上没有被标记的$L$边有$x$条,$R$边有$y$条,那么$i$的贡献就是$c_i(a_i+x)(b_i+y)$
  • 最小化所有点的贡献和
  • $n\le 2\times 10^4;a,b\le 60;c\le 10^9;$树高$\le 40$

• 关于多叉树转二叉树
  • 它死了
  • 它从来就没活过
• 树上背包$\ne$ 把背包放到树上
• 定义：父亲的有用状态数$\le \sum$直接孩子的有用状态数的树型动规问题。
• 优美性质：复杂度$\Theta(nK)$。

• 给定以$1$为根的$n$个点的树，要求砍掉一些边，使得与根相连的点的个数（连通块大小）为$m$。
• 最小化砍掉的边的数量。
• $m\le n \le 3\times 10^3$
• 设$f[i][j]$表示与$i$相连的联通块大小为$j$的最小切割次数。
• 转移：

  for(枚举u的孩子v) {
    for(枚举u的连通块大小k) {
      g[k] = f[u][k]+1;//g为临时数组
    }
    for(枚举u的连通块大小k) {
      for(枚举v的连通块大小j) {
        g[k+j] = min(g[k+j], f[u][k]+f[v][j]);
      }
    }
    for(枚举u的连通块大小k) {
      f[u][k] = g[k];
    }
  }

• 复杂度$?$
• 考虑一个子树的联通块大小最小为$1$，最大为$n$，所以复杂度为$\Theta(n^3)$
• 注意我们枚举$v$连通块大小的时候上界不为$n$，应当为$v$子树大小
• 枚举$u$连通块大小的时候上界不为$n$，也不为$u$子树大小，应当为当前已经决策过的儿子的子树大小和。
• 如果我们这样做了，复杂度会降为$\Theta(n^2)$
• $Why$?
• 晦涩难懂又没用的东西为什么要讲

• 状压动规的特点：
  • 阶段：与普通动规无异。
  • 状态：用$k$进制压缩状态。
  • 转移：往往可以预处理。
  • 由于要$k$进制压缩，所以复杂度一定是指数级，数据范围一定有一项特别小$\le 20$。
  • 复杂度中的底数要尽可能小。

• 约定最低位为第$0$位，编号从低到高依次增加，$x$为我们要进行操作的数字。
• 常见位运算操作：

  1<<k        // 求2的k次方
  x|(1<<k)     // 把第k位置为1
  x&~(1<<k)    // 把第k位置为0
  x^(1<<k)     // 把第k位取反
  (x>>k)&1     // 返回x的第k位
  (x&-x)       // 返回x的最低1位（返回2的次幂而非位数）
  x&((1<<k)-1) // 保留最后k位

• 现有$n$盏灯，初始灯都是开的，以及$m$个按钮。每个按钮都可以控制这$n$盏灯。
• 按下了第$i$个按钮，对于所有的灯都有一个效果，给定矩阵$a[m][n]$来描述，按下$i$按钮对于第$j$盏灯，是下面3中效果之一：
  • 如果$a[i][j]$为$1$，把这盏灯开变关、关变开；
  • 如果是$0$，无论这灯是否开，都不管。
• 求最少按几次按钮关掉所有的灯。
• $n\le 10,m \le 100$
• 设$f[S]$表示使当前灯的状态为$S$所需的最小按按钮次数。
• 发现每个按钮最多按$1$次（异或的性质）。
• 枚举按钮，枚举$S$再转移即可。

• 现有$n$盏灯，初始灯都是开的，以及$m$个按钮。每个按钮都可以控制这$n$盏灯。
• 按下了第$i$个按钮，对于所有的灯都有一个效果，给定矩阵$a[m][n]$来描述，按下$i$按钮对于第$j$盏灯，是下面3中效果之一：
  • 如果为$1$，如果这盏灯开着，把它关上，否则不管；
  • 如果为$-1$，如果这盏灯关着，把它打开，否则不管；
  • 如果是$0$，无论这灯是否开，都不管。
• 求最少按几次按钮关掉所有的灯。
• $n\le 10,m \le 100$
• 设$f[S]$表示使当前灯的状态为$S$所需的最小按按钮次数。
• 转移成环。
• $spfa$。

• 现有$n\times m$的矩阵，有一些位置是$1$，有一些是$0$。
• 请再选择一些位置把$0$变成$1$，要求没有两个$1$相邻（四联通）。
• 求方案数。
• $n\le 200,m \le 10$
• 设$f[S]$表示上一行的$0/1$情况。
• 枚举$S$,枚举$T$，若$S,T$两行相邻合法且$T$合法，则可以转移到$f[T]$。
• 复杂度$\Theta((2^m)^2\times n)=\Theta(4^m\times n)$，勉强通过本题。

• 优化？
• 考虑先枚举$T$，然后$S$的一些位置可以为$1$也可以为$0$，一些位置只能是$0$。
• 令E的第$k$位为$1$表示第一种情况，为$0$表示第二种情况。
• 那么合法能转移的$S$就是$E$的子集。由于若$S$本身不合法$f[S]=0$，所以不需要考虑$E$的子集有不合法情况这件事情。
• 令$g[x]=\sum_{v\text{&}x=v}f[v]$，每次先算出$g$数组再转移$g[E]$即可。
• 根据求$g$数组的不同方法（$3^m\;/\;2^m\times m$），可以做到$\Theta(3^m\times n)$甚至$\Theta(2^m\times m\times n)$
• 子集枚举/高维前缀和。

• 有$n$层点，每层有$m$个，相邻两层之间连有向边（$i$层向$i+1$层）
• 你可以删掉一些点和与它相连的边。
• 求最少删多少点，使得第$1$层无法到达第$n$层。
• $n\le 10^6,m\le 15$

课后练习：luogu 2704 炮兵阵地

• 数位动规的特点：
  • 阶段：以数位为阶段。
  • 状态：往往要用运用技巧简化状态，恒有一维状态表示是否卡上界，常有一维状态表示是否有前导零。
  • 转移：枚举当前位选什么。
  • 通常使用记忆化搜索实现数位动规的代码。

• 标准实现方法:
  • 记忆化搜索
  • 对数字进行扩位，即设最大数字共$k$位，那么把不足$k$位的通过补前导$0$的方式补足$k$位。
  • 即，我们不统计$1,2,50,100$而是$0001,0002,0050,0100$。
  • 这样首先每个数字只会被统计了一次。
  • 其次每个数字位数相同方便统计，只需要记录当前是否是前导$0$不算前导$0$贡献即可。

• 全能喵喵神定义了一种猫数——不含前导零且相邻两个数字之差至少为$2$的正整数被称为猫数。
• 全能喵喵神想知道，在$[l,r]$之间，总共有多少个猫数？
• $l\le r\le 10^{100000}$
• 首先把问题转化成求$[1,r]-[1,l-1]$
• 虽然题目要求不含前导零，但仍然不影响我们扩位统计。
• 设$f[i][k(10)][2][2]$表示填到第$i$位，上一位填的是$k$，是否卡上界，是否是前导$0$，的方案数。
• 转移？

• 求$[l,r]$之间的数中，每个数码出现了多少次。
• $l\le r\le 10^{100000}$
• 首先把问题转化成求$[1,r]-[1,l-1]$
• 设$f[i][k(10)][2][2]$表示填到第$i$位，存的是数码$k$的出现次数，是否卡上界，是否是前导$0$的方案数。
• 转移？

• 求$[l,r]$之间的数中，每个数字二进制下$1$的个数的乘积。
• 以二进制形式给出$l,r$，$l\le r\le 2^{1000}$。
• 首先把问题转化成求$[1,r]-[1,l-1]$。
• 然后设$g[x]$表示二进制下有$x$位$1$的数字有几个，那么答案位$\prod_i i^{g[i]}$
• $2$进制的数位动规不影响扩位。观察发现，前导$0$不会对答案统计产生影响（因为求$1$的个数）。
• 设$f[i][j][2]$表示填到第$i$位，已经填了$j$位$1$，是否卡上界的方案数。
• 转移？

课后练习——luogu4127

• 期望动规的特点：
  • 没有明显的阶段、状态、转移特点。
  • 蕴含数学知识，涉及概率期望、组合数学、公式推导等。
  • 期望倒推、概率正推。
  • 难点在经常遇到概率“悖论”。

• 令$X$表示一个事件，它可以由多种取值，是我们的探讨对象。
• 令$x$表示一种取值，$X=x$表示$X$事件的结果是$x$。
• 令$X|Y=y$表示在$Y=x$的情况下$X$事件
• 独立事件：若$X$事件的结果与$Y$事件的结果毫无关联，则称它们为独立事件。
• 同分布事件：两个变量X,Y的分布相同。
  • 辨析：
  • 掷一枚骰子取值应当如何表示？
  • 掷一枚六面骰子，一枚二十面骰子，取值的和应当如何表示？
  • 掷两枚一模一样的骰子取值的和应当如何表示？
  • 一枚骰子掷两遍取值的和应当如何表示？

• 令$P(X=x)$表示$X$结果为$x$的概率，我们有如下性质：
  • $\sum_{x\in \Omega}P(X=x)=1$
  • 若$X,Y$独立，$P(X=x\textbf{且}Y=y)=P(X=x)P(Y=y)$

• 关于概率有如下公式：
  • 条件概率公式：
    • $P(X=x|Y=y)=\frac{P(X=x\textbf{&&}Y=y)}{P(Y=y)}$
    • $P(Y=y|X=x)P(X=x)=P(X=x\textbf{&&}Y=y)$
    • $P(X=x|Y=y)P(Y=y)=P(X=x\textbf{&&}Y=y)$
  • 全概率公式：
    • $\sum_{y\in \Omega}P(X=x|Y=y)P(Y=y)=P(X=x)$
  • 贝叶斯公式：
    • $P(X=x|Y=y)=\frac{P(Y=y|X=x)P(X=x)}{\sum_{x\in \Omega}P(Y=y|X=x)P(X=x)}$

• 令$E(X)$表示$X$事件的期望取值，我们有如下性质：
  • $E(X)=\sum_{x\in\Omega}P(X=x)x$
  • 期望线性性：$E(aX+bY)=aE(X)+bE(Y)$
  • 若$X,Y$同分布，则$E(X)=E(Y)$
  • 辨析。
  • 若$X,Y$独立，则$E(XY)=E(X)E(Y)$
  • 对于常数$\lambda$，$E(\lambda)=\lambda$

• 关于期望有如下公式：
  • 条件期望公式：
    • $E(X|Y=y)=\sum_{x\in\Omega}xP(X=x|Y=y)$
  • 全期望公式：
    • $E(X)=E(E(X|Y))$
  • 期望方差公式：
    • $V(X)=E((X-E(X))^2)$
    • $V(X)=E(X^2)-E(X)^2$
    • 若$X,Y$独立，$V(X+Y)=V(X)+V(Y)$

• 有$n$个人的队列，$t$秒钟，现在给你每秒钟队头那个人上电梯的概率，每秒最多一人上电梯。
• 求$t$秒钟后，在电梯上人的数量的期望。
• $n,t\le {10^3}$
  • 考虑设$f[i][j]$表示$i$时刻已经有$j$个人上电梯的概率，然后进行概率$dp$，最后枚举人数套用期望定义式即可。
• $t \le n \le 10^6$
  • 设$f[i]$表示第$i$时刻的期望电梯人数。
  • $f[i]=(f[i-1]+1)\times p_i+f[i-1]\times (1-p_i)$

• 假设有n种不同的卡牌，每个卡牌出现的概率相同，买一包干脆面可以随机获得一张卡牌？
• 求集齐所有卡牌，买干脆面的期望。
• $n\le 10^3$。
• 设$f[i]$表示还差$i$张卡牌的期望值，初始$f[n]=0$，求$f[0]$。
• $f[i]=f[i-1]\times\frac{i}{n}+f[i]\times\frac{n-i}{n}+1$。

课后习题：百度“codeforces 概率dp”大概有20~30道。

• 高斯消元解决期望概率dp，
  • 对于动规中转移有环的情况，我们可以用$spfa$来解决。
  • 但是由于概率期望dp是转移的多个项之间复杂的嵌套，我们只能使用高斯消元来解决。
• 矩阵快速幂优化dp
  • 小测试：你会矩阵快速幂吗？
  • 用于解决普通一维递推型的动规，或者是两维动规但是每一维可以分开使用矩阵快速幂。

• 令$f[i] = f[i - 1] * a + b$，给$f[0],a,b,n$，求$f[n]$。
• $n\le 10^9$
• 令$f[i][j] = \begin{cases} f[i][j-1] * a + b &j\ne 1 \\f[i-1][m]*c+d&j=1 \end{cases}$
• 给$f[1][1],a,b,c,d,n,m$，求$f[n][m]$。
• $n,m\le 10^9$

• 现有一个$n$行$m$列的棋盘，一只马欲从棋盘的左上角跳到右下角。
• 每一步它向右跳奇数列，且跳到本行或相邻行。
• 跳越期间，马不能离开棋盘。
• $n\le 50;m\le 10^9$

• 用于优化$f[i]=max(g[i]\times h[j]+w[j])$型的动规。
• 将$h[j]$看做$x$，将$w[j]$看做$y$，那么$g[i]$便是斜率$k$，$f[i]$便是截距。
• 合法的$f[i]$值就是合法的截距值，也就是所有将点$(h[j],w[j])$带入所得到的的截距。
• 我们想让$f[i]$（截距）最大，相当于有一条斜率为$g[i]$的直线从上向下扫，遇到的第一个$(h[j],w[j])$的点时的截距。
• 考虑从上向下扫只会遇到凸壳上的点，所以维护凸壳并二分即可。
• 另一种推式子理解。

• 实现方法：
  • 斜率递增/递减：单调队列。
  • 斜率任意：单调队列+二分。
  • 决策集合左右端点不降：单调队列多个删除对首情况。
  • 决策集合左右端点任意：平衡树维护凸壳/李超树。

• 给定长度为$n$的序列$a[]$和常数$L$，要求划分成若干段。
• $[i,j]$一段的代价是：
  • 令$X=j-i+\sum_{k=i}^j a[k]$
  • 代价为$(X-L)^2$
• $n\le 10^5$

• 略。