什么是动态规划
动态规划通过额外的空间将已经搜索过的相似的结果（指某些具有相同性质解的集合）用一个数组存起来，所以DP中的状态转移看上去是某两三个值之间的推导，其实是某两三个集合之间的状态转移！
常见的线性DP问题
- 最长上升子序列
- 最长公共子序列
- 最短编辑距离
- 数字三角形
最长上升子序列
典型题例：
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
示例 ：
输入：第一行包含整数 N。 第二行包含 N 个整数，表示完整序列。品的体积和价值 7 3 1 2 1 8 5 6 输出： 4
思路
状态表示：集合f[i]表示以第i个数结尾的上升子序列的集合；属性：为集合中max
状态计算：第i的数固定，则以集合第i-1为哪个数进行集合划分，（0 ~ i-1）
f[i] = max(f[j] + 1), 条件：a[j] < a[j],j = 0,1,3,...i-1;
时间复杂都计算：状态数量状态转移的数量–> nn 为O(n^2)
代码：
#include <iostream> #include <cstring> using namespace std; const int N = 1010; int n; int a[N], f[N]; int main() { cin >> n; for (int i = 1; i <= n; i ++) scanf("%d",&a[i]); for (int i = 1; i <= n; i ++) { f[i] = 1; //只有a[i] for (int j = 1; j < i; j ++) if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1); } int res = 0; for (int i = 1; i <= n; i ++) res = max(res, f[i]); printf("%d\n", res); return 0; }
最长公共子序列
典型题例：
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
示例 ：
输入：第一行包含两个整数 N 和 M。 第二行包含一个长度为 N 的字符串，表示字符串 A。 第三行包含一个长度为 M 的字符串，表示字符串 B。 字符串均由小写字母构成。 4 5 acbd abedc 输出： 3
思路
状态表示：集合f[i,j]：所有A[1i]与b[1j]的公共子序列的集合；属性：max
状态计算：在f[i-1,j-1], f[i-1,j], f[i,j-1], f[i-1,j-1]+1 四个集合中的最大值
因为f[i-1,j], f[i,j-1]已经包含f[i-1,j-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() { cin >> n >> m >> a + 1 >> b + 1; // for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) { f[i][j] = max(f[i - 1][j], f[i][j - 1]); // if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1); } cout << f[n][m] << endl; return 0; }
传送门：动态规划- 背包问题总结（二）
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
