9.15

[Ryanlyt]

动态规划

核心：状态的表示和状态的转移（偏数学，没有模板） Dp：状态表示f(i, j)（集合（所有选法、条件{1、只从前i个物品中选出；2、总体积<= j}）、属性（Max，Min，数量）），状态计算 Dp优化：一般都是对动态规划的代码或者计算方程做一个等价变形（先把基本的形式写出再考虑优化）

背包问题

N, V, vi, wi

• 01背包 每件物品最多用一次

• 完全背包 每件物品有无限个

• 多重背包 每件物品有Si个 优化

• 分组背包 分组，限制每一组里只能选一个

[Ryanlyt]

线性DP

下标从0开始还是从1开始：如果涉及到下标[i - 1]一般从1开始，否则从0开始

状态表示：能做出来的情况下，维数越少越好

DP问题里面用枚举

数字三角形

最长上升子序列 把序列存储下来（动态规划问题求方案：把转移记录下来）

最长公共子序列（注意子序列和子串的区别） 当属性为max、min时，划分的子问题可以有重复；求数量时，划分的子问题不能有重复

[Ryanlyt]

区间DP

先循环区间长度（从小到大），再循环区间左端点，再枚举决策 要保证每一个要算的状态所依赖的状态都已算好了 石子合并

[Ryanlyt]

计数类DP

整数划分

• 可以看成是完全背包问题

• 用其他思路

[Ryanlyt]

数位统计DP

计数问题

[Ryanlyt]

状态压缩DP

蒙德里安的梦想：把nm的棋盘分成若干个12的长方形，有多少种方案 f(i, j)：从i列上一列捅出来的方格的行数，j看作二进制数

最短哈密尔顿路径 f(i, j)：所有从0走到j，走过的所有点是i的所有路径 状态被压缩到了i里，用二进制数表示 先枚举所有状态，再枚举所有转移的状态（指循环写法上的先后）

n比较小的时候可以考虑能不能用状态压缩dp

[Ryanlyt]

树形DP

没有上司的舞会 f(u, 0)：所有从以u为根的子树中选择，并且不选u这个点的方案 f(u, 1)：所有从以u为根的子树中选择，并且选u这个点的方案 该题没有告诉根节点是谁，需要用写has_father判断一下：root从1开始枚举，root++，直到没有父节点为止

[Ryanlyt]

记忆化搜索

动态规划的一种实现方式，递归求解（每一道动态规划都可以用递归来写，递归的方式更容易理解） （树形dp是一种特殊的递归方式） 优点：好写，代码复杂度小

滑雪 f(i, j)：所有从(i, j)开始滑的路径 先判断，把所有存在的情况枚举一遍 要递归地算每个点的状态：先把每个状态初始化为-1，表示每个状态都没有被算过，然后算最大值，枚举从每个点出发 上下左右技巧：用偏移量