动态规划

注：数据范围：n<=1000；自底向上；下标i-1/从1开始
一.转态表示
1.集合：感性认识
2.属性：max；min；数量 （注：抽象–>集合内存储的是什么值）

二.状态计算
1.def：集合的划分
（通过感性理解，拆分子问题）

背包问题

01背包

一.基础知识
注：每件物品最多只用一次
1.物品；使用次数 –> 最大价值

二.实现
1.状态表示
f(i,j)
1）集合：所有选法的集合 （从i个物品选+总体积<=j）
2）属性：集合（选法中的）总价值max
2.状态计算
子集的表示：
1）（不含i）–> f(i-1,j)
2）（含i）–> f(i-1,j-vi)+wi
注：j>vi时，情况才成立
3.综上：f(i,j)=max(上述两种情况1、2）

三.优化
注：二维–>一维
1.j从v[i]再开始考虑
2.j从后往前遍历（保证取到i-1）

完全背包

注：每件物品不限制次数

多重背包

注：每个物品有限个

分组背包

注：物品有多组，每组最多选一个（互斥）

线性DP

一.基础知识
1.拥有明显递推线性顺序

（一）数字三角形

注：数据范围：n<500

一.基础知识
1.状态表示
f(i,j) 即第i行第j列
1）集合:所有从起点（1,1）走到（i,j）的路径
2）属性：max（路径之和的max）

2.状态计算
1）来自左边 –> f(i-1,j-1)+a(i,j)
2）来自右边 –> f(i-1,j)+a(i,j)

3.综上：f(i,j)=max(上述两种情况1、2）

二.实现
难点1.取max避开边界判断：先进行初始化（INF）+多一位（i+1:0开始）

（二）最长上升子序列

注：线性要求：单增+是子序列 ；数据范围：n<1000

一.基础知识
1.状态表示
f(i)
1）集合：所有以第i个数结尾的上升子序列的集合（包含多个）
2）属性：max（集合内的最长的）

2.状态计算
i –> 以i-1进行分析：f(j)+1 (第j类，以j,i来结尾)

3.综上：f(i)=max(f(j)+1) j=0,1,2…

（三）最长公共子序列

注：线性要求：公共子序列；数据范围：n<1000；字符串” “表示；

一.基础知识
1.状态表示
f(i,j)：两个序列
1）集合：所有在第一个序列的前i个字母中出现，且在第二个序列的前j个字母中出现的公共子序列 （字符串的经验表示）
2）属性：max（长度的最大值）

2.状态计算
a(i)和b(j)是否包含在子序列中（结尾字母）
1）00 –> f(i-1,j-1) 注：被包含在01；10中
2）01 –> f(i-1,j)
3）10 –> f(i,j-1)
4）11 –> f(i-1,j-1)+1

3.综上：
1）f(i,j)=max(01;10)
2）特判11存在情况：f(i,j)=max（情况1、2）

区间DP

注：状态定义的是一个区间；（经验）按区间长度从小到大进行循环

（一）石子合并

注：数据范围 n<300
一.基础知识
1.状态表示
f(i,j)：
1）集合：所有将第i堆石子到第j堆石子合并成一堆石子的合并方式（感性理解：合并方式）
2）属性：min（代价最小）

2.状态计算
分析：最后一次合并时的分界线位置k：左边[i,k]和右边[k+1,j] k=i…j-1

3.综上：最小代价 ：f(i,j)=min(左边+右边+(s(j)-s(i-1))) (前-倒数第二次+倒数第一次/即石子重量)

计数类DP

注：

数位统计DP

状态压缩DP

树形DP

记忆化搜索

注：DP的一种实现方式：递归

（一）滑雪

一.基础知识
1.状态表示
f(i,j)：
1）集合：所有从（i,j）开始滑的路径
2）属性：max(路径的最长值)

2.状态计算
从路径方向分析：
1）上
2）右：–> f（i,j+1）+1
3）左：
4）下：