DP：
【1】状态表示：需要几个维度来表示状态
（1）集合（所有选法，带有约束条件）
（2）属性（最大值、最小值、数量）
【2】状态计算：如何算出每一步的状态，对应集合的划分（不重+不漏）
**DP的优化：**对代码/计算方程做变形
https://www.cnblogs.com/littlehb/p/15366309.html
01背包：每件物品最多只用一次
条件：
【1】只从前i个物品当中选
【2】总体积小于等于j
状态计算方式：含i的情况+不含i的情况
f
(
i
,
j
)
=
m
a
x
(
f
(
i
−
1
,
j
)
,
f
(
i
−
1
,
j
−
v
i
)
+
w
j
)
f(i,j)=max(f(i-1,j),f(i-1,j-v_i)+w_j)
f(i,j)=max(f(i−1,j),f(i−1,j−vi)+wj)
# include dp优化：转化成1维数组
【1】f(i)只用到了f(i-1)，因此可用滚动数组
【2】j和j-vi都是小于等于j的，在j的一侧而不是两侧，因此可用1维数组
# include 完全背包：每件物品可用无限次
状态计算方式：
f
(
i
,
j
)
=
m
a
x
(
f
(
i
−
1
,
j
)
,
f
(
i
−
1
,
j
−
v
i
∗
k
)
+
w
j
∗
k
)
f(i,j)=max(f(i-1,j),f(i-1,j-v_i*k)+w_j*k)
f(i,j)=max(f(i−1,j),f(i−1,j−vi∗k)+wj∗k)
k ∗ v i < = j k*v_i<=j k∗vi<=j
# include dp优化：转化成2维数组
【1】将f(i,j)的k次max操作展开
f
[
i
,
j
]
=
m
a
x
(
f
[
i
−
1
,
j
]
,
f
[
i
−
1
,
j
−
v
i
]
+
w
i
,
f
[
i
−
1
,
j
−
2
v
i
]
+
2
w
i
,
f
[
i
−
1
,
j
−
3
v
i
]
+
3
w
i
,
.
.
.
)
f[i,j]=max(f[i-1,j],f[i-1,j-v_i]+w_i,f[i-1,j-2v_i]+2w_i,f[i-1,j-3v_i]+3w_i,...)
f[i,j]=max(f[i−1,j],f[i−1,j−vi]+wi,f[i−1,j−2vi]+2wi,f[i−1,j−3vi]+3wi,...)
【2】f(i,j-v)的k次max操作展开
f
[
i
,
j
−
v
]
=
m
a
x
(
f
[
i
−
1
,
j
−
v
i
]
,
f
[
i
−
1
,
j
−
2
v
i
]
+
w
i
,
f
[
i
−
1
,
j
−
3
v
i
]
+
2
w
i
,
.
.
.
)
f[i,j-v]=max(f[i-1,j-v_i],f[i-1,j-2v_i]+w_i,f[i-1,j-3v_i]+2w_i,...)
f[i,j−v]=max(f[i−1,j−vi],f[i−1,j−2vi]+wi,f[i−1,j−3vi]+2wi,...)
【3】分析可得，f(i,j)的状态转移可以变成是f(i-1,j)+w的结果
f
[
i
,
j
]
=
m
a
x
(
f
[
i
−
1
,
j
]
,
f
[
i
]
[
j
−
v
i
]
+
w
i
)
f[i,j]=max(f[i-1,j],f[i][j-v_i]+w_i)
f[i,j]=max(f[i−1,j],f[i][j−vi]+wi)
合并之后可得：
# include 多重背包：每个物品个数不一样，不是无限，也不是只有一个，有ki的个数限制
状态转移方程：
f
(
i
,
j
)
=
m
a
x
(
f
(
i
−
1
,
j
)
,
f
(
i
−
1
,
j
−
v
i
∗
k
)
+
w
j
∗
k
)
，
k
从
0
到
s
i
f(i,j)=max(f(i-1,j),f(i-1,j-v_i*k)+w_j*k)，k从0到s_i
f(i,j)=max(f(i−1,j),f(i−1,j−vi∗k)+wj∗k)，k从0到si
# include dp优化：打包物体（二进制拆分）
# include 分组背包：N组，每组里面若干个，每组里面最多使用一个物品，比如水果组选择了苹果，就不能选香蕉
# include 题目：数字三角形
# include 题目：最长上升子序列
# include 存储状态转移过程
# include 题目：最长公共子序列
# include 题目：石子合并
# include 题目：整数划分
一个正整数 n 可以表示成若干个正整数之和，n=n1+n2+…+nk
现在给定一个正整数 n，请求出 n 共有多少种不同的划分方法
【二维】
把整数n看成一个容量为n的背包，有n种物品，物品的体积分别是1~n。
我们要求的是 恰好 装满背包的方案数(计数)，每种物品 可以用无限次，所以可以看成是一个完全背包。
状态表示
f[i,j]：从前i中选，总和是j的选法，值就是方案数量。
i个物品选择了0个f[i−1,j] ：在前i个物品中选择，结果现在第i个物品选择了0个，就是说这j个体积都是前i−1贡献的。i个物品选择了s个f[i−1,j−s∗i]初值
求最大值时，当都不选时，价值是 0。
求方案数时，当都不选时，方案数是 1。
#include 【一维】
#include 题目：计数问题
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。
#include 题目：蒙德里安的梦想
先放横的，再放竖的
当前摆完横着的小方块之后，剩余的位置，如果能用竖着的小方块 填满 就合法，否则不合法
如果每一列所有连续空着的小方块个数存在奇数个，必然填充不满（不合法情况）
状态表示
f
[
i
]
[
j
]
：已经摆完前
i
列，且第
i
列的状态为
j
的所有方案
f[i][j]：已经摆完前i列，且第i列的状态为j的所有方案
f[i][j]：已经摆完前i列，且第i列的状态为j的所有方案
f【0】【i】中，除了f【0】【0】都是非法的，所以赋值为0
最终结果
已经摆完第m列，并且第m列的状态为0，也就是第m列没有任何一个小方格新去摆放横条
#include v[M] 是一个二维数组，初始化比较麻烦，需要用循环遍历第一维，然后再v[i].clear()进行清空
v[i].clear();
// 状态i,从哪些状态转化而来？
for (int j = 0; j < 1 << n; j++) // j为前序状态
// (1) i & j==0 同一行不能同时探出小方格，那样会有重叠
// (2) 解释一下ok[i | j]
// 比如: 01000 | 10101 = 11101,描述当前完成状态叠加后的最终状态，在预处理的数组中找一下，是不是合法状态
if ((i & j) == 0 && ok[i | j]) v[i].push_back(j);
}
// 多组数据，每次清零
memset(f, 0, sizeof f);
// 初始方案数
f[0][0] = 1; // 可以理解为 从虚拟的第0开始（第一个0），还没有向右探出小方格（第二个0），此时的方案数只有1种。
// 如果你想为什么不是0种，下面的递推关系就会让你明白，0做为基底，就啥也递推不出来了。
// DP正式开始
for (int i = 1; i <= m; i++)
for (int j = 0; j < 1 << n; j++) // 遍历第i列的所有状态j
for (auto k : v[j]) // 遍历第i-1列的所有状态k
f[i][j] += f[i - 1][k]; // 每个合法状态，均需从它的前序有效状态转移而来
// 输出答案
cout << f[m][0] << endl;
}
return 0;
}
题目：最短Hamilton路径
#include 题目：没有上司的舞会
f [ u , 0 ] ：所有以 u 为根的子树中选，并且不选 u 这个点的方案 f[u,0]：所有以u为根的子树中选，并且不选u这个点的方案 f[u,0]：所有以u为根的子树中选，并且不选u这个点的方案
f [ u , 1 ] ：所有以 u 为根的子树中选，并且选 u 这个点的方案 f[u,1]：所有以u为根的子树中选，并且选u这个点的方案 f[u,1]：所有以u为根的子树中选，并且选u这个点的方案
状态转移
f
[
u
,
0
]
=
∑
m
a
x
(
f
(
s
o
n
,
0
)
,
f
(
s
o
n
,
1
)
)
f[u,0]=∑max(f(son,0),f(son,1))
f[u,0]=∑max(f(son,0),f(son,1))
f [ u , 1 ] = ∑ f ( s o n , 0 ) f[u,1]=∑f(son,0) f[u,1]=∑f(son,0)
#include 递归求解DP问题——记忆化搜索
题目：滑雪
分4个方向讨论：上下左右
#include