1.最长公共子序列
给定两个长度分别为 N和M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3
一、可以用二维dp，dp[i] [j] 表示在第一个序列的第i位到第二个序列的j位的最长公共子串的长度。
二、二维数组要想给每一个赋值，即需要从底往上遍历。
三、讲遇到的情况分成两大类，一类是相等，一类是不等。
即状态转移方程我为
if(a[i] == b[j])
dp[i][j] = dp[i-1][j-1] + 1 ;
else if(a[i] != b[j])
dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) ;
具体代码如下:
#include
using namespace std ;
const int N = 1010 ;
int f[N][N] ;
char a[N], b[N] ;
int main()
{
int n , m ;
cin >>n >> m ;
for(int i = 1 ; i <= n ;++i)
cin >> a[i] ;
for(int j = 1 ; j <= m ;++j)
cin >> b[j] ;
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= m ; ++j)
{
if(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] < 二、最长上升子序列
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
数据范围给的比较大，所以直接暴力dp就可以了。
一、创建一个一维的dp数组，dp[i]表示的是从1到i的字串中， 以q[i]所结尾的子序列的最长子序列的长度.
二、dp思路，搜索数组中目标值前面的值，找到严格比target小的index， 将本target接在后面即可。然后一直比较，将最大的值赋给dp即可。
三、最终的结果不一定是最后的dp结果，而是过程中出现最大的值，因此需要在每一个小循环结束的时候，设置一个res，专门用来记录出现的最大的dp值。
代码如下：
#include
using namespace std ;
const int N = 1010 ;
int w[N] ;
int f[N] ;
int main()
{
int n ;
cin >>n ;
int res =0 ;
for(int i = 1 ; i <= n ;++i)
{
cin >> w[i] ;
}
for(int i = 1 ; i <= n ;++i)
{
f[i] = 1 ;
for(int j = 1 ; j <= i ;++j)
{
if(w[i] > w[j]) f[i] = max(f[i] , f[j] +1) ;
}
res = max(res , f[i]) ;
}
cout << res < 三、最长上升子序列II
题目同二，但是数据范围从1000改到了1e5。
所以，直接把暴力给毙了.
我们想到最多可以用nlogn来优化，于是可以用二分来优化.
dp是用不了了，可以用贪心加二分。
具体思路：
一、对于原数组中的值，依次在二分数组中找到小于他的最大值，二分数组的作用是一边存储，一边用于搜索。
二、最后返回q数组的长度即可。
#include
using namespace std ;
const int N = 100010 ;
int w[N] ;
int q[N] ;
int main()
{
int n ;
cin >> n ;
q[0] = -2e9 ;
for(int i = 1 ; i <= n ;++i)
{
cin >> w[i] ;
}
int len = 0 ;
for(int i = 1 ; i <= n ;++i)
{
int left = 0 ; int right = len ;
while(left < right)
{
int mid = (left + right +1) >> 1 ;
if(q[mid] < w[i])
{
left = mid ;
}
else
{
right = mid - 1 ;
}
}
q[right+1] = w[i] ;
len = max(len , right+1) ;
}
cout << len < 
