Acwing 线性DP

状态转移方程呈现出一种线性的递推形式的DP，我们将其称为线性DP。

Acwing 898.数字三角形

实现思路：

• 对这个三角形的数字进行编号，状态表示依然可以用二维表示，即f(i,j),i表示横坐标（横线），j表示纵坐标（斜线）
  
  
• 用f(i,j)表示到点(i,j)的路径最大数字之和。对集合进行划分，到达某点(i,j)只可能经过左上方的点(i-1,j-1)或右上方的点(i-1,j)。用a[i][j]表示当前点的数值；
• 故可得状态转移方程：f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j])

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>using namespace std;const int N = 510, INF = 1e9;  
int n; 
int a[N][N];  // 存储三角形中的数字
int f[N][N];  // 动态规划数组，存储从顶点到达每个位置的最大路径和int main() {cin >> n;  for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {cin >> a[i][j];  }}// 初始化 DP 数组，将所有 f[i][j] 初始化为一个极小值，表示不可到达for (int i = 0; i <= n; i++) {for (int j = 0; j <= i + 1; j++) {f[i][j] = -INF;}}// 设置起始点，顶部元素的最大路径和就是它自身f[1][1] = a[1][1];// 状态转移方程：f[i][j] 表示到达第 i 行第 j 列的最大路径和for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {// 到达 f[i][j] 位置有两种可能：// 1. 来自 f[i-1][j-1]，即从左上角过来// 2. 来自 f[i-1][j]，即从正上方过来f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);}}// 在最后一行的所有位置中找出最大值int res = -INF;for (int i = 1; i <= n; i++) {res = max(res, f[n][i]);  // 找出最后一行的最大路径和}cout << res << endl;  return 0;
}

这道题还可以从下往上递推，考虑f[i][j]来自左下方和来自右下方两种情况，这样就不需要处理边界问题，而且最后的结果一定集中在f[1][1]中。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 510, INF = 1e9;  // 定义常量 N 为最大行数，INF 为极大值
int n;  // 表示三角形的行数
int f[N][N], a[N][N];  // f 用于存储从底部到达每个位置的最大路径和，a 存储三角形中的数字int main() {int n;cin >> n;  // 输入三角形的行数// 输入三角形中的数字for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)cin >> a[i][j];// 初始化：将最后一行的值作为初始状态for (int i = 1; i <= n; i++) f[n][i] = a[n][i];// 自底向上递推，计算每一行的最大路径和for (int i = n - 1; i >= 1; i--) {for (int j = 1; j <= i; j++) {// f[i][j] 表示在 (i, j) 位置的最大路径和f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];}}// 输出顶点处的最大路径和cout << f[1][1] << endl;return 0;
}

Acwing 895.最长上升子序列

实现思路：

• 一维数组f[i]表示以第i个数为结尾的最长递增子序列的长度；
• 状态划分：选定i为结尾的递增子序列，则再从[0,i-1]中筛选出倒数第二个位置的数，使递增子序列的长度最大。注意这个倒数第二个位置的数必须满足a[j]<a[i]，这样才能保证递增序列；
• 状态转移方程为f[i]=max(f[i],f[j]+1);

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010; int n; 
int a[N], f[N];  // a 存储输入的数组, f 存储以每个元素结尾的最长上升子序列的长度int main(){cin >> n;  for(int i = 1 ; i <= n ; i ++) cin >> a[i];  // 动态规划计算最长上升子序列for(int i = 1 ; i <= n ; i ++) {f[i] = 1;  // 初始状态，每个元素自身可以作为一个长度为1的子序列for(int j = 1 ; j < i ; j ++){// 如果前面的元素 a[j] 比当前元素 a[i] 小，则可以考虑将 a[i] 接在 a[j] //之后形成一个更长的子序列if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);  // 更新 f[i]，选择使 f[i] 最大的方案}}// 找到 f 数组中的最大值，即最长上升子序列的长度int res = 0;for(int i = 1 ; i <= n ; i ++) res = max(res, f[i]);cout << res << endl;  return 0;
}

那有没有办法进行优化呢？最长上升子序列（LIS）问题的时间复杂度为$O(n^2),$我们可以通过贪心算法 + 二分查找来将时间复杂度优化为$O(nlogn)$.

Acwing 896. 最长上升子序列 II

实现思路：

• 首先在上述解法的基础上，假如存在一个序列3 1 2 5，以3结尾的上升子序列长度为1，以1为结尾的上升子序列长度也为1，这是两个长度一样的上升子序列（伏笔：结尾元素1<3）。在继续向后遍历查找时，看3这个序列，当出现一个比3大的数时，以3结尾的上升子序列就会更新，比如遍历到5了，那么上升序列变为3 5；同时注意到这个5一定会加入到以1结尾的上升序列中（因为1<3，那么1<5的），那么含有1的上升序列长度一定是>=2的，因为中间可能存在<3但>1的数（比如这里就有2，序列长度就更新为3）。可以看出存在3的这个序列就不需要枚举了，因为存在1的序列往后遍历的长度是一定大于你这个存在3的序列的（前提是以1结尾和以3结尾的上升序列长度相等），那我找最长的时候怎么都轮不到包含3的序列头上，那我一开始在1和3结尾的序列之后直接舍弃枚举包含3的序列了（去掉冗余）。
• 在以上的分析得到：当存在两个上升序列长度相同时，结尾数更大的序列可以舍去不再枚举，所以每次就干脆选出相同长度结尾元素最小的序列继续操作
• 那么状态表示更改为：f[i]表示长度为i+1(因为下标从0开始)的最长上升子序列，末尾最小的数字。(所有长度为i+1的最长上升子序列所有结尾中，结尾最小的数) 即长度为i的子序列末尾最小元素是什么。
• 状态计算：序列长度+1(cnt++)，当前末尾最小元素变为a[i]。 **若a[i]小于等于f[cnt-1],**说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个 大于或等于(不能直接写大于，要保证单增) a[i]的数的位置mid，将这个数a[i]放在mid的位置（其实就是找到a[i]适合存在的位置，不改变序列长度）。

具体实现代码（版本一）：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;const int N = 100010;  // 定义最大数组大小
int n, cnt;
int a[N], f[N];int main() {// 输入数组长度cin >> n;// 输入数组元素for (int i = 0; i < n; i++) {cin >> a[i];}// 初始化 cntcnt = 0;// 处理第一个元素f[cnt++] = a[0];for (int i = 1; i < n; i++) { // 注意这里应为 i < nif (a[i] > f[cnt - 1]) {f[cnt++] = a[i]; // 如果 a[i] 大于当前上升序列末尾的数，则末尾加入} else {// 使用二分查找int l = 0, r = cnt - 1;while (l < r) {int mid = (l + r) / 2;if (f[mid] >= a[i]) r = mid; // 找到第一个 >= a[i] 的位置else l = mid + 1;}f[r] = a[i]; // 替换找到的位置}}cout << cnt << endl; // 输出最长上升子序列的长度return 0;
}

版本二（使用lower_bound函数，找到第一个 >= a[i] 的位置）

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;const int N = 100010;  // 定义最大数组大小
int n;
int a[N];int main() {// 输入数组长度cin >> n;// 输入数组元素for (int i = 0; i < n; i++) {cin >> a[i];}// 用于维护当前的上升子序列vector<int> d;// 遍历数组的每个元素for (int i = 0; i < n; i++) {// 使用二分查找找到第一个 >= a[i] 的位置auto it = lower_bound(d.begin(), d.end(), a[i]);if (it == d.end()) {// 如果没有找到比 a[i] 大的元素，则将 a[i] 添加到序列末尾d.push_back(a[i]);} else {// 否则，用 a[i] 替换掉找到的这个位置的元素*it = a[i];}}// 最终 d 的大小就是最长上升子序列的长度cout << d.size() << endl;return 0;
}

Acwing 897. 最长公共子序列

实现思路：

• f(i,j)表示第一个序列的前i个字母中出现并且在第二序列前j个字母中出现的最长的公共子序列长度
• 状态可划分为4种情况：a[i]表示为第一个序列中第i个字符，b[j]表示第二个子序列中第j个字符
  • 00：表示最长公共子序列中一定不包含字符a[i]和b[j]，用f[i-1][j-1]表示
  • 01：表示最长公共子序列中一定不包含字符a[i]，一定包含b[j]。不能用f[i-1][j]表示（不是等价的），因为f[i-1][j]表示的是该公共子序列一定不包含a[i]，但b[j]不一定，可能包含也可能不包含。故f[i-1][j]是包含01这种情况的。但是由于求的是最大子序列的长度（而不是具体元素），所以求解的时候可以用f[i-2][j]来求解
  • 10：表示最长公共子序列中一定包含字符a[i]，一定不包含b[j]。用f[i][j-1]求解，但含义不等价，同上。
  • 11：表示最长公共子序列中一定包含字符a[i]和b[j]，用f[i-1][j-1]+1表示，但注意需要满足a[i] = b[j]才行，因为公共子序列，既然包含a[i]、b[i]，那么两者必然相等才行
• 00的情况实质上已经被包含在01、10两种情况之中，所以可以省略，故只需求下面三种状态

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;char a[N], b[N];
int f[N][N];
int n, m;int main() {cin >> n >> m;// 输入字符串，保留 a[0] 和 b[0] 为空字符cin >> (a + 1) >> (b + 1);// 动态规划计算最长公共子序列for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {// 如果字符相同，则长度加 1if (a[i] == b[j]) {f[i][j] = f[i - 1][j - 1] + 1;} else {// 否则取上方或左方的最大值f[i][j] = max(f[i - 1][j], f[i][j - 1]);}}}// 输出最长公共子序列的长度cout << f[n][m] << endl;return 0;
}