线性DP
类似于背包问题，即状态的转换是以线性递推的形式进行的。分析问题的方式同样是闫式DP的方法。下面是几道例题。
数字三角形
题目
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数 n，表示数字三角形的层数。
接下来 n行，每行包含若干整数，其中第 i 行表示数字三角形第 i层包含的整数。
输出格式
输出一个整数，表示最大的路径数字和。
数据范围
1≤n≤500 −10000≤三角形中的整数≤10000
输入样例
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例
30
思考
首先考虑状态的表示，dp[i][j]表示走到第i行j列元素的所有走法长度的集合，集合的属性是最大值。
然后考虑集合的划分，这里考虑由上向下走，下向上走的思路也是一样的。每一个dp[i][j]都可以由上方的dp[i - 1][j - 1]或dp[i - 1][j]走一步得到，也就是dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + d[i][j]。
其次我们需要考虑状态的初始化，首先dp[1][1] = d[1][1]，因为第一步是确定的。然后我们可以发现边权是有负数的，所以我们需要将状态初始化为一个比较小的数，注意由于左右边界没有状态，但是在状态转移中可能会取到，所以初始化时左右需要多初始化一列。
最后遍历最下面一行取最大值。
代码
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 5e2 + 10;
const int INF = 1e9;
int n,m;
int dp[N][N], d[N][N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
cin >> d[i][j];
// 路径中存在负数，初始化为一个较小的数
for (int i = 0; i <= n; i ++ )
for (int j = 0; j <= i + 1; j ++ )
dp[i][j] = -INF;
dp[1][1] = d[1][1];
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + d[i][j];
}
}
int res = -INF;
for(int i = 1; i <= n; i++) res = max(dp[n][i], res);
cout << res;
return 0;
}
// 状态表示
// 走到第i行j列的路径集合，max
// 状态计算
// dp[i][j]
// dp[i - 1][j - 1] + d[i][j]
// dp[i - 1][j] + d[i][j]
// 状态初始化
// dp[1][1] = d[1][1]
最长上升子序列
题目
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000， −109≤数列中的数≤109
输入样例
7
3 1 2 1 8 5 6
输出样例
4
思考
首先是状态的表示， dp[i]表示包含第i个数的最长上升子序列长度，集合的属性是最大值。
然后是状态的计算也就是集合的划分，因为子序列没有要求连续，所以每一个i前面的元素都有可能和i组成上升子序列，所以需要两层循环，dp[i] = dp[j] + 1，条件是s[i] > s[j]。
最后是状态的初始化，每一个元素自身构成了一个长度为一的上升子序列，所以dp数组所有元素初始化为一。
代码
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int n;
int dp[N];
int s[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> s[i];
for(int i = 1; i <= n; i++)
{
dp[i] = 1;
for(int j = 1; j < i; j++)
{
if(s[i] > s[j]) dp[i] = max(dp[i], dp[j] + 1);
}
}
int res = 0;
for(int i = 1; i <= n; i++) res = max(res, dp[i]);
cout << res;
return 0;
}
// 状态划分
// dp[i] 包含第i个数的最长上升子序列
// 集合属性
// max
// 状态计算
// s[i] > s[j] => dp[i] = dp[j] + 1
// 状态初始化
// dp[i] = 1
优化
当数据量大了，上面的代码就无法通过，下面通过规律加二分将复杂度降低到nlogn。
对于以下数列：3 1 4 5，我们可以发现对于长度为2的上升子序列3 4和1 4，我们完全可以不存3 4，因为如果3可以构成上升子序列，那么1也一定可以构成。我们可以开一个数组q用来存放不同长度下，结尾最小的最长上升子序列的结尾值。
同时，有这样一个规律，对于q数组，它一定是严格单调递增的，证明如下：
设q是已经经过处理的数组，它的每个元素都是结尾最小的最长上升子序列的结尾值，q[i]为长度为i的结尾最小的最长上升子序列，如果有q[i] >= q[i + 1]，则以q[i + 1]为结尾的上升子序列，它的前i个数字构成的上升子序列的结尾值就一定小于等于q[i]，那么就和假设相悖，证明完毕。
这样我们就有一个严格单调递增的序列，可以遍历元素，通过二分不断的去维护q数组，直到遍历完成，q数组的长度就是能达到的最大值。
下面是代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], q[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int len = 0;
for(int i = 1; i <= n; i++)
{
int l = 0, r = len;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}
cout << len;
return 0;
}
最长公共子序列
题目
给定两个长度分别为 N 和 M 的字符串 A和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例
4 5
acbd
abedc
输出样例
3
思考
状态划分，dp[i][j]用来表示 a字符串的前i个字符和b字符串的前j个字符的公共子串长度的集合，注意是前i个字符，不一定包含第i个字符。集合的属性是最大值。
状态计算，看上去可以将集合划分为dp[i - 1][j - 1] + 1、dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1]，表示对于a的第i个字符和b的第j个字符，第一种情况：在a[i] == b[j]的条件下都选，第二种情况：都不选，后面两种是选择其中一个。
但是，对于dp[i - 1][j]，它的实际含义是a字符串的前i-1个字符和b字符串的前j个字符的公共子串长度的集合，它不等同于只包含第j个字符的集合。多出来的那一部分实际上是dp[i - 1][j - 1]的一部分，但是好在集合的属性是求最大值，所以不影响。其实我们可以看出dp[i - 1][j]、dp[i][j - 1]多出的部分恰好组成了dp[i - 1][j - 1]，所以d[]i - 1][j - 1]可以不用去写。
代码
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int n, m;
char a[N], b[N];
int dp[N][N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++) cin >> b[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if(a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
cout << dp[n][m];
return 0;
}
// 状态划分
// dp[i][j] a字符串的前i个字符和b字符串的前j个字符的公共子串的集合
// 集合的属性
// 最大值
// 状态的计算
// dp[i][j]
// max(dp[i - 1][j], dp[i][j - 1])
// a[i] == b[j] => dp[i - 1][j - 1] + 1
// 状态的初始化
// 无
编辑距离
题目
给定 n 个长度不超过 1010 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。
对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含一个字符串，表示给定的字符串。
再接下来 m 行，每行包含一个字符串和一个整数，表示一次询问。
字符串中只包含小写字母，且长度均不超过 1010。
输出格式
输出共 m 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。
数据范围
1≤n,m≤1000
输入样例
3 2
abc
acd
bcd
ab 1
acbd 2
输出样例
1
3
思考
对于每两个字符串之间，可以使用线性DP的方式解题。
对于状态划分，dp[i][j]表示由a字串转换为b字串所需步骤的集合。集合的属性是最小值。
对于状态的划分，我们可以发现dp[i][j]可以由dp[i - 1][j] + 1、dp[i][j - 1] + 1、dp[i - 1][i - 1]、dp[i - 1][j - 1] + 1，分别代表对a进行增加一个操作，对a进行删除一个的操作，第i个字符和第j个字符相等，所以不需要操作，第i个字符和第j个字符不相等，进行替换操作。
状态的初始化，对于dp[i][0]和dp[0][i]，分别是删除i个字符和增加i个字符。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int dp[N][N];
char strs[N][N];
int work(char a[], char b[])
{
int la = strlen(a + 1), lb = strlen(b + 1);
for(int i = 0; i <= la; i ++) dp[i][0] = i;
for(int i = 0; i <= lb; i ++) dp[0][i] = i;
for(int i = 1; i <= la; i ++)
{
for(int j = 1; j <= lb; j ++)
{
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (a[i] != b[j]));
}
}
return dp[la][lb];
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> (strs[i] + 1);
while (m -- )
{
char d[N];
int limit;
int res = 0;
cin >> (d + 1) >> limit;
for(int i = 0; i < n; i++)
if(work(strs[i], d) <= limit)
res ++;
cout << res << endl;
}
return 0;
}