动态规划（Dynamic Programming,DP）算法通常用于求解某种具有最优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应一个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似，其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中 得到原有问题的解。与分治法不同的是，动态规划经分解后得到的子问题往往不是相互独立的。
01背包：
fix(i,j)=max(fix(i-1,j),fix(i-1,j-v)+w);完全背包:
fix(i,j)=max(fix(i-1,j),fix(i,j-v)+w);背包问题求方案数：（设置一个cnt数组初始化为1，与dp同步更改）
const int N = 1010;
const int mod=1e9+7;
int f[N];
int g[N];
int cnt[N];
int cntt[N];
int main( ) {
int n, v;
cin >> n >> v;
for (int i = 0; i <= v; i++)
cnt[i] = 1;
for (int i = 0; i < n; i++) {
memcpy(g, f, sizeof(f));
memcpy(cntt, cnt, sizeof(cntt));
int a, b;
cin >> a >> b;
for (int j = a; j <= v; j++) {
int x = g[j - a] + b;
if (x > g[j]) {
cnt[j] = cntt[j - a];
f[j] = x;
} else if (x == g[j]) {
cnt[j] = (cntt[j] + cntt[j - a])%mod;
}
}
}
cout << cnt[v]%mod;
return 0;
}
树形dp（有依赖的背包问题）：
const int N = 110;
int e[N], ne[N], idx, h[N];
int v[110];
int w[110];
int n, V;
int f[110][110];
int g[110][110];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//p是根节点，先假设当前节点必须选，那么他的子树就是分组背包
void dfs(int a) {
for (int i = v[a]; i <= V; i++) {
f[a][i] = w[a];
}
for (int u = h[a]; u != -1; u = ne[u]) {
int b = e[u];
dfs(b);
}
for (int u = h[a]; u != -1; u = ne[u]) {
memcpy(g,f,sizeof(f));
int b = e[u];
for(int i=v[a];i<=V;i++)
{
for (int z = v[b]; z <= i-v[a]; z++)
f[a][i] = max(f[a][i],max(g[a][i], g[a][i - z] + g[b][z]));
}
}
}
多重背包:
二进制化简法：对于有s个物品的物品，将s分解为1+2+4+….pow(2,k)+s的背包，从而化简为01背包
int k = 1;
while (k < s)
{
vi[cnt] = v * k;
wi[cnt] = w * k;
s = s - k;
k = k * 2;
cnt++;
}
vi[cnt] = v * s;
wi[cnt] = w * s;
cnt++;
单调队列：
（滑动窗口求最大值）q队列保存下标
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
int q[100000+10];
int hh=0,tt=-1;
for(int i=0;i<nums.size();i++)
{
tt++;
q[tt]=i;
if(q[tt]-q[hh]>=k)
hh++;
while(hh<tt&&nums[q[tt-1]]<nums[q[tt]])
{
tt--;
q[tt]=i;
}
if(i>=k-1)
ans.push_back(nums[q[hh]]);
}
return ans;
}
多重背包究极版：
（使用拷贝数组） 注意到每一个模v的同余组，是相互独立的，且最大同时存在值一定，那么可以使用单调队列计算每一个窗口里面最大值，这里并不是直接把f中的数字拿出来，而是单纯比较，用队列存取较大值的下标。
const int N = 20010;
int f[N];
int g[N];
int q[N];
int main( ) {
int n, V;
cin >> n >> V;
for (int i = 1; i <= n; i++) {
int v, w, s;
cin >> v >> w >> s;//体积，价值，数量
memcpy(g,f,sizeof(f));
for (int j = 0; j < v; j++) {
int hh = 0, tt = -1;//模拟单调队列
for (int z = j; z <= V; z = z + v) {
tt++;
q[tt] = z;
if (hh < tt && (q[tt] - q[hh]) / v > s )
hh++;
while (hh < tt && (q[tt] - q[tt - 1]) / v * w + g[q[tt - 1]] <= g[q[tt]]) {
q[tt - 1] = q[tt];
tt--;
}
f[z] = g[q[hh]] + (z - q[hh]) / v * w;
}
}
}
cout << f[V];
return 0;
}
最长上升子序列
初始化：数组中的第一个数
循环数组的所有数，若该数小于已有序列的最大数，则把该数代替已有序列中第一个大于他的数（二分查找）,且该数的dp值就是这个数在序列中的位置，总复杂度nlog(n),最后得到最大序列长度即为所求;
最长公共子序列
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (a[i-1] == b[j-1])
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}寻找最少的上升子序列数量：核心思想是贪心，对于每一个数，要么加入比他小的第一个数的后面，要么重新开一个序列，比如6,4,2那么5就要把4替换掉，1就直接push_back，注意到上升子序列的vector是降序，下降子序列是升序。
for (int i = 1; i <= n; i++) {
if (!f.size()) {
f.push_back(an[i]);
} else if (f[f.size() - 1] < an[i]) {
f.push_back(an[i]);
} else
for (int j = 0; j < f.size(); j++) {
if (an[i] <= f[j]) {
f[j] = an[i];
break;
}
}
}
int ans2 = f.size();
int ans1 = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (an[j] >= an[i]) {
w[i] = max(w[i], w[j] + 1);
ans1 = max(ans1, w[i]);
}
}
}最短编辑距离
（两个字符串编辑dp[i][j]次后相等）
void help(int a, int b, string s1, string s2)//s1.size=a,s2.size=b;
{
for (int i = 0; i <= b; i++)//初始化
{
dp[0][i] = i;
}
for (int i = 0; i <= a; i++)//初始化
{
dp[i][0] = i;
}
for (int i = 1; i <= a; i++)
{
for (int j = 1; j <= b; j++)
{
if (s1[i-1] == s2[j-1])
{
dp[i][j] = minn(dp[i - 1][j - 1], dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}
else
{
dp[i][j] = minn(dp[i - 1][j - 1]+1, dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}
}
}
}
石子合并
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。特别的，如果是环形石子，可以初始化为2n倍，后面的是前面的复制，比如说：1,3,2,5,2 -> 1,3,2,5,2,1,3,2,5,2 正常求，然后求[1-1+n-1]的最大值就可以了。
for (int i = 1; i <= n; i++)//初始化
{
dp[i][i] = 0;
}
for (int i = 2; i <= n; i++)
{
for (int j = i - 1; j >= 1; j--)
{
for (int k = j; k < i; k++)
{
dp[j][i] = min(dp[j][i],dp[j][k]+ dp[k + 1][i]);
}
dp[j][i] = dp[j][i] + s[i] - s[j - 1];
}
}状态机：
0是持有股票的状态，1是未持有股票的状态，除了f[0][0][0]以外f[0][0-k][0,1]都是不合法的，f[1-n][0][0]也是不合法的。
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int f[N][110][2];
int w[N];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
memset(f, 0, sizeof(f));
for (int i = 0; i <= k; i++) {
f[0][i][0] = -INF;
f[0][i][1] = -INF;
}
for (int i = 0; i <= n; i++) {
f[i][0][0] = -INF;
}
f[0][0][1] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++) {
f[i][j][0] = max(f[i - 1][j - 1][1] - w[i], f[i - 1][j][0]);
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] + w[i]);
}
int ans = 0;
for (int i = 1; i <= k; i++) {
ans = max(ans, max(f[n][i][0], f[n][i][1]));
}
cout << ans;
return 0;
}
状态压缩DP
主要先找出来一行所有合法的状态，在这一行合法的状态中找出两两合法的上下行，遍历。
typedef long long ll;
const int N = 1 << 12, M = 110;
vector<int> state;
vector<int> head[N];
ll f[13][M][N];
int cnt[N];
int n, k;
bool check(int a) {
for (int i = 0; i < n; i++) {
if ((a >> i & 1) && (a >> i + 1 & 1))
return false;
}
return true;
}
int countt(int a) {
int res = 0;
for (int i = 0; i < n; i++) {
res += a >> i & 1;
}
return res;
}
int main() {
cin >> n >> k;
for (int i = 0; i < 1 << n; i++) {
if (check(i)) {
state.push_back(i);
}
}
for (int i = 0; i < state.size(); i++) {
cnt[i] = countt(state[i]);
}
for (int i = 0; i < state.size(); i++) {
for (int j = 0; j < state.size(); j++) {
if (check(state[i] | state[j]) && (state[i] & state[j]) == 0) {
head[i].push_back(j);
}
}
}
memset(f, 0, sizeof(f));
f[0][0][0] = 1;
for (int i = 1; i <= n + 1; i++) {
for (int j = 0; j <= k; j++) {
for (int a = 0; a < state.size(); a++) {
for (auto b : head[a]) {
if (j >= cnt[a])
f[i][j][a] += f[i - 1][j - cnt[a]][b];
}
}
}
}
cout << f[n + 1][k][0];
return 0;
}
