练习题（动态规划）
一，最长上升子序列2
题目：
思路分析：
之前的最长上升子序列的时间度是O(n^2)，同时集合划分是按以第 i - 1 个数是几来划分的，状态转移方程也很简单是 f[i] = f[j] + 1 ，最后取所有一个max
那怎么优化呢？考虑一个每次求的时候有没有冗余
例如：3 1 2 1 8 5 6
如果一个数能接在3后面，那一定可以接在1后面，对吧，那1就比这个3好，所以如果我们能接在以一个大点的数结尾的上升子序列后面，那就一定可以接在以一个小一点的数结尾的上升子序列后面，以此为启发 我们可以存储前面每种长度的最长上升子序列的结尾的最小值是多少，我们可以存到数组里面去。
我们可以猜测一下，随着上升子序列的长度的增加，子序列结尾的数一定是严格单调递增的，
假如长度为6的上升子序列的结尾最小值是a1，长度为5的子序列的结尾最小值是a2，如果a1小于 a2 ，那么我们一定可以从长度为6的子序列里面截取一个长度是5的最长上升子序列，并且结尾小于a2，那么长度为5的上升子序列的结尾就一定不是a2。
这样就矛盾了，所以整个序列一定是严格单调递增的。
假设，我们想求一下当前这个数 ai，以ai结尾的最长子序列，那我们要从序列里找到一个最大的小于ai的序列，假设长度为4的上升子序列的最小结尾值是q4，q4是最大的小于等于ai的数，那把ai接过去，那这样我们就得到了一个以ai结尾的长度为5的上升子序列，假设长度为5的上升子序列的最小结尾是q5，由于q4是最大的小于等于ai的，那么q5就是大于等于ai的，所以ai一定不可能接到长度是5的子序列后面，因此，以ai结尾的上升子序列的最大长度就是5，那如何找到最大的小于等于ai的数呢？可以用二分O(logn)。然后更新一下q5，变成ai。因为找到了新的长度是5的上升子序列的最小结尾。
一共n个数，二分logn，那么一共 O(n*logn)
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int q[N]; // 存储所有不同长度的上升子序列的结尾的最小值
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
int len = 0; // 初始化最长上升子序列的长度
q[0] = -2e9; // 初始化 q[0] 为一个小于所有数组元素的值，方便后续比较
for (int i = 0; i < n; i ++ ) // 遍历每个数
{
int l = 0, r = len; // 二分查找那个最大的小于等于ai的数
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 << endl;
}二，最短编辑距离
题目：
思路：
依旧是dp的思路框，dp为什么快呢，他就是对暴搜的优化，可以用一个数来表示一堆东西
这里是按最后一步是删除，增加还是改变来分的，，假如是删除，那应该是把 a 的1到i - 1跟b的1到 j 匹配，再删除ai，这样才一样，所以第一类的最小值应该是 f[i - 1, j ] + 1。假如是增加一个字母，添加完后两字符串相等，那其实就说明在添加之前，a的 1 到 i 已经和 b 的 1 到 j - 1 匹配了，然后添加一个之后，两字符串相等，那第二类的最小值赢是 f[i, j - 1] + 1。假如是改，改完之后相等了，那改之前应该是 a 的前 i - 1个字母和 b的j - 1的字母匹配上，如果a[i] != b[j] 那就加一步改，如果相等了，那就不加了，所以第三类是 f[i - 1, j - 1] + 1/0（1或者0）；
综上 f[i, j] = min(f[i - 1, j] +1, f[i, j - 1] + 1, f[i - 1, j - 1] + 1/0) ，这就是这个题的状态转移方程；
代码：
#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()
{
cin >> n >> a + 1;
cin >> m >> b + 1;
// 初始化
for (int i = 0; i <= m; i ++ ) f[0][i] = i; // 将空字符串转换为 b 的前 i 个字符需要 i 次插入操作
for (int i = 0; i <= n; i ++ ) f[i][0] = i; // 将 a 的前 i 个字符转换为空字符串需要 i 次删除操作
// dp
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);
}
cout << f[n][m] << endl; // 结果就是让两个字符长相等f[n][m]
return 0;
}三，编辑距离
题目：
思路：
没什么思路，就跟上一个题一样的，不过只是判断了一下是否在限制内，直接上代码吧
代码：
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 15, M = 1010;
int n, m; // n 是字符串的数量 m 是询问次数
int f[N][N];
char str[M][N]; // 存储输入的字符串数组
// 计算两个数组的编辑距离 跟上个是一样的
int edit_distance(char a[], char b[])
{
int la = strlen(a + 1), lb = strlen(b + 1);
for (int i = 0; i <= lb; i ++ ) f[0][i] = i;
for (int i = 0; i <= la; i ++ ) f[i][0] = i;
for (int i = 1; i <= la; i ++ )
for (int j = 1; j <= lb; j ++ )
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
}
return f[la][lb];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> str[i] + 1;
while (m -- )
{
char s[N]; // 询问的字符串
int limit; // 限制
cin >> s + 1 >> limit;
int res = 0;
for (int i = 0; i < n; i ++ )
if (edit_distance(str[i], s) <= limit)
res ++ ;
cout << res << endl;
}
return 0;
}