规划院网站建设书,专做ppt的网站,学校官方网站建设,pc端浏览器手机版前言#xff1a;
本系列是看的B站董晓老师所讲的知识点做的笔记
董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)
树塔-记忆化搜索
特点#xff08;前提#xff09;#xff1a;从上向下的累加和是不能重复使用的#xff0c;从下向上的累加和是可以重… 前言
本系列是看的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];//说明已经全部遍历完了elsef[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],yyp[x][y]进行输出
最长上升子序列
B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
动态规划On²
for (int i 1; i n; i) f[i] 1;//把初始化化长度都设为1for (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];}
全部代码
#includeiostream
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 i1; istrlen(a); i){for(int j1; jstrlen(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)maxf[i][j];}
编辑距离
题目
P2758 编辑距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
二维思路 一维思路 具体分析
1.初始化看上面的矩阵第一行的意思是“LOVER此时是空串则“NOTV”那里有几个字符就需要删除几个字符 for(int i1;ila;i) f[i][0]i;for(int i1;ilb;i) f[0][i]i;
2. 一维思路如果不清楚的话就对照着图片上方的四个格子推一次
总结
1.LISLongest Increasing Subsequence 最长递增子序列
LCSLongest Common Subsequence 最长公共子序列
2.公共子串:字符必须是连续相等的
公共子序列:字符必须是相等的可以不连续。
