什么是动态规划
动态规划通过额外的空间将已经搜索过的相似的结果（指某些具有相同性质解的集合）用一个数组存起来，所以DP中的状态转移看上去是某两三个值之间的推导，其实是某两三个集合之间的状态转移！.
常见的线性DP问题
- 最长上升子序列
- 最长公共子序列
- 最短编辑距离
- 数字三角形
最短编辑距离
典型题例：
给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
1.删除–将字符串 A 中的某个字符删除。
2.插入–在字符串 A 的某个位置插入某个字符。
3.替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出，将 A 变为 B 至少需要进行多少次操作。。
示例 ：
10 AGTCTGACGC 11 AGTAAGTAGGC 输出： 4
思路
状态表示：集合f[i,j]表示所有将a[1 ~ i]变成b[1~j]的操作方式：属性：min
状态计算：删；f[i-1,j]+1 增：f[i,j-1]+1 改：f[i-1,j-1]+0/1; 有i-1操作输入字符串从下标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); //输入字符串从下标1开始 scanf("%d%s", &m, b + 1); //处理边界 for (int i = 0; i <= m; i ++) f[0][i] = i; //注意边界的处理i<=m 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 ++) { f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]); else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1); } printf("%d\n", f[n][m]); return 0; }
数字三角
典型题例：
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
示例 ：
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出： 30
思路
状态表示：f[i, j], 表示从底向上走到[i, j] 的所有路线的集合；属性：最大值
状态计算：集合划分（从底向上走不需要考虑边界）f[i, j] = max(f[i+1, j]+w[i,j], f[i+1, j+1)+w[i,j])
代码：
#include <iostream> #include <cstring> using namespace std; const int N = 510; int n; int w[N][N], f[N][N]; //w为原始三角矩阵 int main() { cin >> n; //处理输入 for (int i = 1; i <= n; i ++) for (int j = 1; j <= i; j ++) cin >> w[i][j]; //初始化最低边界 for (int i = 1; i <= n; i ++) f[n][i] = w[n][i]; for (int i = n - 1; i; i--) for (int j = 1; j <= i; j ++) f[i][j] = max(f[i + 1][j] + w[i][j], f[i + 1][j + 1] + w[i][j]); cout << f[1][1] << endl; return 0; }
传送门：动态规划- 背包问题总结（一）
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
