一、数字三角形模型

1. 摘花生(最大值)

原题链接
原题链接

#include<iostream>using namespace std;const int N = 1010;int f[N][N];
int n;int main()
{cin >> n;while(n--){int x,y;cin >> x >> y;for(int i = 1; i <= x; i++){for(int j = 1; j <= y; j++){cin >> f[i][j];}}for(int i = 1; i <= x; i++){for(int j = 1; j <= y; j++){f[i][j] += max(f[i-1][j],f[i][j-1]);}}cout << f[x][y] << endl;}return 0;
}

2. 最低通行费(需要把边界置成0x3f)

我的错题点

1. 数组开大一点
2. 这个题求的是最小值，所以需要把临界值置成最大值
   原题链接
   原题链接

#include<iostream>using namespace std;const int N = 110;int g[N][N];
int f[N][N];
int n,m;int main()
{cin >> n;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)cin >> g[i][j];for(int i = 2; i <= n; i++)f[0][i] = 0x3f3f3f3f,f[i][0] = 0x3f3f3f3f;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){f[i][j] = min(f[i-1][j],f[i][j-1]) + g[i][j];}cout << f[n][n];return 0;
}

3. ★★★ 取方格数

路径长度为k,第一条路线到x1=i,第二条路线到x2=j的所有方案

原题链接

#include <bits/stdc++.h>using namespace std;const int N = 15, M = 2 * N;int n;//方格图的边长 
int w[N][N];
int f[M][N][N];int get(int i, int j, int k)
{return max(max(f[k - 1][i - 1][j - 1], f[k - 1][i][j - 1]), max(f[k - 1][i - 1][j], f[k - 1][i][j]));//转移方程，分成 4 种考虑
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;int x, y, z;while (cin >> x >> y >> z, x || y || z) w[x][y] += z;for (int k = 2; k <= 2 * n; ++ k)for (int i = 1; i < k; ++ i)for (int j = 1, v; j < k; ++ j){f[k][i][j] = get(i, j, k) + w[i][k - i];if (i != j) f[k][i][j] += w[j][k - j];//!!!}cout << f[2 * n][n][n] << endl;return 0;
}

4. ★★★★★ 传纸条

就是 取方格数 的 题意延申一下

原题链接
原题链接

#include <bits/stdc++.h>using namespace std;const int N = 59, M = 2 * N;int n, m;//方格图的边长 
int w[N][N];
int f[M][N][N];int get(int i, int j, int k)
{return max(max(f[k - 1][i - 1][j - 1], f[k - 1][i][j - 1]), max(f[k - 1][i - 1][j], f[k - 1][i][j]));
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;int x, y, z;for(int i = 1;i <= n;++ i)for(int j = 1;j <= m;++ j)cin >> w[i][j];for (int k = 2;k <= m + n;++ k)for (int i = 1;i < k;++ i)for (int j = 1;j < k;++ j){f[k][i][j] = get(i, j, k) + w[i][k - i];if (i != j) f[k][i][j] += w[j][k - j];}cout << f[m + n][n][n] << endl;return 0;
}

0x51 线性dp

经典例题：LIS LCS 数字三角形

✔例1. ★★★ Mr Young’s Picture Permutations

原题链接

f[a][b][c][d][e]代表从后往前每排人数分别为a, b, c, d, e的所有方案的集合, 其中a >= b >= c >= d >= e

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 31;int n;
LL f[N][N][N][N][N];int main()
{while (cin >> n, n){int s[5] = {0};for (int i = 0; i < n; i ++ ) cin >> s[i];memset(f, 0, sizeof f);f[0][0][0][0][0] = 1;for (int a = 0; a <= s[0]; a ++ )for (int b = 0; b <= min(a, s[1]); b ++ )for (int c = 0; c <= min(b, s[2]); c ++ )for (int d = 0; d <= min(c, s[3]); d ++ )for (int e = 0; e <= min(d, s[4]); e ++ ){LL &x = f[a][b][c][d][e];if (a && a - 1 >= b) x += f[a - 1][b][c][d][e];if (b && b - 1 >= c) x += f[a][b - 1][c][d][e];if (c && c - 1 >= d) x += f[a][b][c - 1][d][e];if (d && d - 1 >= e) x += f[a][b][c][d - 1][e];if (e) x += f[a][b][c][d][e - 1];}cout << f[s[0]][s[1]][s[2]][s[3]][s[4]] << endl;}return 0;
}作者：yxc
链接：https://www.acwing.com/solution/content/4954/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

✔例2. 最长公共上升子序列

原题链接

a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合

#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;const int N = 3010;int n;
int a[N], b[N];
int f[N][N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);for (int i = 1; i <= n; i ++ ){int maxv = 1;for (int j = 1; j <= n; j ++ ){f[i][j] = f[i - 1][j];if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);}}int res = 0;for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);printf("%d\\n", res);return 0;
}作者：yxc
链接：https://www.acwing.com/solution/content/4955/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

关键思路

1. dp很复杂，以bi结尾fi，j这样就会减少复杂度
2. maxv记录是什么
   由普遍算法 推广到 优化代码的过程理解了 就知道maxv存储的是什么了

✔例3. 分级

原题链接

比较不错的题解

f[i][j] 代表所有给A[1] ~ A[i]分配好了值且最后一个B[i] = A’[j]的方案的集合；

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;const int N = 2010, INF = 0x3f3f3f3f;int n;
int a[N], s[N];
int f[N][N];
int ans;int work()
{for (int i = 1; i <= n; i ++ ) s[i] = a[i];sort(s + 1, s + 1 + n);for (int i = 1; i <= n; i ++ ){int mn = INF;for (int j = 1; j <= n; j ++ ){mn = min(mn, f[i - 1][j]);f[i][j] = mn + abs(a[i] - s[j]);}}int res = INF;for (int i = 1; i <= n; i ++ ) res = min(res, f[n][i]);return res;
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);ans = work();reverse(a + 1, a + 1 + n);ans = min(ans, work());printf("%d\\n", ans);return 0;
}作者：种花家的兔兔
链接：https://www.acwing.com/solution/content/136108/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

✔例4. 移动服务

f[i][x][y]表示已经处理完前i个请求，且三个服务员分别在p[i], x, y的所有方案的集合；

原题链接

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 210, M = 1010, INF = 0x3f3f3f3f;int n, m;
int w[N][N];
int f[M][N][N];
int p[M];int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )scanf("%d", &w[i][j]);for (int i = 1; i <= m; i ++ ) scanf("%d", &p[i]);p[0] = 3;memset(f, 0x3f, sizeof f);f[0][1][2] = 0;for (int i = 0; i < m; i ++ )for (int x = 1; x <= n; x ++ )for (int y = 1; y <= n; y ++ ){int z = p[i], v = f[i][x][y];if (x == y || x == z || y == z) continue;int u = p[i + 1];f[i + 1][x][y] = min(f[i + 1][x][y], v + w[z][u]);f[i + 1][z][y] = min(f[i + 1][z][y], v + w[x][u]);f[i + 1][x][z] = min(f[i + 1][x][z], v + w[y][u]);}int res = INF;for (int x = 1; x <= n; x ++ )for (int y = 1; y <= n; y ++ ){int z = p[m];if (x == y || x == z || y == z) continue;res = min(res, f[m][x][y]);}printf("%d\\n", res);return 0;
}作者：yxc
链接：https://www.acwing.com/solution/content/4957/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

✔例5. 传纸条

f[k, i, j] 表示两个人同时走了k步，第一个人在 (i, k - i) 处，第二个人在 (j, k - j)处的所有走法的最大分值。

原题链接

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 55;int n, m;
int g[N][N];
int f[N * 2][N][N];int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )scanf("%d", &g[i][j]);for (int k = 2; k <= n + m; k ++ )for (int i = max(1, k - m); i <= n && i < k; i ++ )for (int j = max(1, k - m); j <= n && j < k; j ++ )for (int a = 0; a <= 1; a ++ )for (int b = 0; b <= 1; b ++ ){int t = g[i][k - i];if (i != j || k == 2 || k == n + m){t += g[j][k - j];f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);}}printf("%d\\n", f[n + m][n][n]);return 0;
}作者：yxc
链接：https://www.acwing.com/solution/content/3954/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

✔补充相关例题：取方格数

路径长度为k,第一条路线到x1=i,第二条路线到x2=j的所有方案

原题链接

#include <bits/stdc++.h>using namespace std;const int N = 15, M = 2 * N;int n;//方格图的边长 
int w[N][N];
int f[M][N][N];int get(int i, int j, int k)
{return max(max(f[k - 1][i - 1][j - 1], f[k - 1][i][j - 1]), max(f[k - 1][i - 1][j], f[k - 1][i][j]));//转移方程，分成 4 种考虑
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;int x, y, z;while (cin >> x >> y >> z, x || y || z) w[x][y] += z;for (int k = 2; k <= 2 * n; ++ k)for (int i = 1; i < k; ++ i)for (int j = 1, v; j < k; ++ j){f[k][i][j] = get(i, j, k) + w[i][k - i];if (i != j) f[k][i][j] += w[j][k - j];//!!!}cout << f[2 * n][n][n] << endl;return 0;
}

✔例6. I-区域★★★★★

原题链接

✔例7. 饼干

原题链接

二、线性DP

1. 数字三角形 ✔1.6

★f[i][j] 从下到上 走到f[i][j]的所有路径的最大值
原题链接
原题链接

#include<iostream>using namespace std;const int N = 510;int f[N][N];int main()
{int n;cin >> n;for(int i = 1; i <= n; i++)for(int j = 1; j <= i; j++)cin >> f[i][j];for(int i = n-1; i >= 1; i--)for(int j = 1; j <= i; j++)f[i][j] += max(f[i+1][j],f[i+1][j+1]);cout << f[1][1];return 0;
}

2. ☆ 最长上升子序列

双重循环

f[i] 以第i个数结尾的 上升子序列的最大值

原题链接

#include<iostream>using namespace std;const int N = 1010;int a[N],f[N];int main()
{int n;cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];for(int i = 1; i <= n; i++){f[i] = 1;for(int j = 1; j <= i; j++){if(a[i] > a[j])f[i] = max(f[i],f[j]+1);}}int res = 0;for(int i = 1; i <= n; i++)res = max(res,f[i]);cout << res;return 0;
}

3. ☆ 最长上升子序列 II

★f[i] 存储 最长上升子序列的 示范串

★ 二分 + dp优化

原题链接

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5+10;int n;
int f[N],st[N];int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> f[i];int len;st[1] = f[1];len = 1;for(int i = 2; i <= n; i++){int pos = lower_bound(st+1,st+1+len,f[i])-st;st[pos] = f[i];len = max(len,pos);}cout << len;return 0;
}

4. ☆ 最长公共子序列

★f[i][j]表示a的前i个字母，和b的前j个字母的最长公共子序列长度

原题链接

思路 (在推导示例时，可以总结出)

1. f[i][j] 表示什么需要先想清楚。
   表示的是：在i，j组合的情况下，的最大子串 长度
   所以当 i，j相等时
   f[i][j] = f[i-1][j-1] + 1
   不相等的时候
   f[i][j] = max(f[i-1][j],f[i][j-1]);

#include<iostream>using namespace std;const int N = 1010;int f[N][N];
int n,m;
char a[N],b[N];int main()
{cin >> n >> m >> a+1 >> b+1;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(a[i]==b[j])f[i][j] = f[i-1][j-1] + 1;elsef[i][j] = max(f[i-1][j],f[i][j-1]);}}cout << f[n][m];return 0;
}

5. ☆ 最短编辑距离

原题链接

★f[i][j] 所有把a中的前i个字母 变成 b中前j个字母的集合的操作集合

做题总结

1. 由于需要用到前面的数据，所以一定用dp
2. i j 相等则 在 i - 1 j-1 的基础 +1
3. 如果不相等 则按着 所可以操作的步骤 + 1

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n, m;
char a[N], b[N];
int f[N][N];int main()
{scanf("%d%s", &n, a + 1);scanf("%d%s", &m, b + 1);for (int i = 0; i <= m; i ++ ) f[0][i] = i;for (int i = 0; i <= n; i ++ ) f[i][0] = i;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ ){if (a[i] == b[j]){f[i][j] = f[i-1][j-1];}else{f[i][j] = min(f[i-1][j] + 1, f[i - 1][j - 1] + 1);f[i][j] = min(f[i][j],f[i][j-1]+1);}}printf("%d\\n", f[n][m]);return 0;
}

6. 编辑距离( 和上题差不多 )

原题链接