前言：
本系列是看的B站董晓老师所讲的知识点做的笔记
董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)
树塔-记忆化搜索
特点（前提）：从上向下的累加和是不能重复使用的，从下向上的累加和是可以重复使用的
把题目变成二叉树的形式：4的左子树分别是下一行的8和下一行右边的3，依次类推，每一个树的左子树都是他的下一行的数和下一行数的右边的那个数
int a[9][9] =
{ {1},
{4,6},
{8,3,9},
{5,7,2,1}};
int n = 4;
int f[9][9];//记录从上向下的累加和
int dfs(int x, int y)
{
if (f[x][y] != 0) return f[x][y];//说明该点已经遍历过
if (x == n - 1) f[x][y] = a[x][y];//说明已经全部遍历完了
else
f[x][y] = a[x][y] + max(dfs(x + 1, y), dfs(x + 1, y + 1));
return f[x][y];
}线性DP
数塔
int calu(int x, int y)
{
int x, y;
for (x = n - 2; x >= 0; x--)
for (y = 0; y <= x; y++)//这样就可以弄成塔的形式
a[x][y] += max(a[x + 1][y], a[x + 1][y + 1]);
cout << "max=" << a[x][y];
}如果需要输出路径的话，需要有一个前驱路径数组p[x][y]和一个备份数组b[x][y];
前驱路径数组主要是记录y的增值的，把两种情况（a[x + 1][y]>/<=a[x + 1][y + 1]）分别设为0和1,r然后在通过遍历数组b[x][y],y=y+p[x][y]进行输出
最长上升子序列
B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
动态规划（O（n²））
for (int i = 1; i <= n; i++) f[i] = 1;//把初始化化长度都设为1
for (int i = 2; i <= n; i++)
{
for (int j = 1; j < i; j++)
if (a[i] > a[j]) f[i] = max(f[j] + 1,f[i]);//分别依次计算不同下标时候的长度
for (int i = 1; i <= n; i++) ans = max(ans, f[i]);//遍历寻找长度最长的长度
}
二分查找
思想：
新进来一个元素a[i]:
（1)大则添加：如果a[i]大于b[len],直接让b[++len]=a[i]。即b数组的长度增加1，而且添加了一个元素。
（2）小则替换：如果a[i]小于或等于b[len]，就用a[i]替换掉b数组中第一个大于或等于a[i]的元素。
假设第一个大于a[i]的元素是b[j],那么用a[i]换掉b[j]后，会使得b[1...j]这个上升子序列的结尾元素更小。对于一个上升子序列，其结尾元素越小，越有利于续接其它元素，也就越可能变得更长。
注意:
b数组不是存储的最长上升子序列，但是子序列的长度相同
核心代码
二分查找第一个大于等于x的位置
int find(int x) {
int l = 1, r = len, mid;
while (l <= r) {
int mid = l + r >> 1;
if (x > b[mid]) l = mid + 1;
else r = mid - 1;
}
return l;
}新增元素代码
for (int i = 0; i < n; i++) {
if (b[len] < a[i]) b[++len] = a[i];
else b[find(a[i])] = a[i];
}全部代码
#include<iostream>
using namespace std;
const int N = 10010;
int n, a[N], b[N], len;
int find(int x) {
int l = 1, r = len, mid;
while (l <= r) {
int mid = l + r >> 1;
if (x > b[mid]) l = mid + 1;
else r = mid - 1;
}
return l;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
b[0] = -2e9;
for (int i = 0; i < n; i++) {
if (b[len] < a[i]) b[++len] = a[i];
else b[find(a[i])] = a[i];
}
printf("%d\n", len);
return 0;
}
最长公共子序列
1.最长公共子序列不是连续的一段区间
2.记录路径的时候前驱数组可以去掉
1.思路
2.核心代码
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
else f[i][j] = max(f[i - 1][j - 1], max(f[i - 1][j], f[i][j - 1]));3.题目一
P1439 【模板】最长公共子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前提：
两个排列都是1到n的排列，说明元素都是相同的只是顺序不同，
思路：
把LCS转换成LIS
原因：
通过离散化可以得到一个性质。
离散化步骤：
A:3 2 1 4 5
B:1 2 3 4 5
重新把A,B数组中的元素替换掉，使得A数组是其次递增的
标个号:把3标成a,把2标成b，把1标成c.…于是变成:
A: a b c d e
B: c b a d e
结论：最长公共子串的长度不会改变，又因为A数组是递增的，所以说在B数组中递增的子序列就是A的子序列
离散化代码：
for (int i = 1; i <= n; i++)
{
cin >> m;
line[m] = i;
}最长公共子串
核心代码
for(int i=1; i<=strlen(a); i++){
for(int j=1; j<=strlen(b); j++){
if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=0;
if(f[i][j]>max)
max=f[i][j];
}编辑距离
题目
P2758 编辑距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
二维思路
一维思路
具体分析
1.初始化，看上面的矩阵，第一行的意思是“LOVER"此时是空串，则“NOTV”那里有几个字符就需要删除几个字符
for(int i=1;i<=la;i++) f[i][0]=i;
for(int i=1;i<=lb;i++) f[0][i]=i;2. 一维思路如果不清楚的话，就对照着图片上方的四个格子推一次
总结：
1.LIS：Longest Increasing Subsequence 最长递增子序列
LCS：Longest Common Subsequence 最长公共子序列
2.公共子串:字符必须是连续相等的；
公共子序列:字符必须是相等的，可以不连续。
