进阶版的序列DP 从一道题的优化开始
ModricWang的序列问题
题目描述：给定一个序列，求出这个序列中的最长上升子序列的长度。
这道题的本质还是求解一个最长上升子序列的问题
相对与之前提到过的O（n^2）的算法 我们可以重新整理思路
用O(nlogn)的思路来写，用贪心和二分优化之前的算法
我们设置新的DP数组//dp[i]代表的是当前长度为i的上升子序列的末尾元素的大小
状态转移方程为如果dp[len] < ar[i] 那么就将数ar[i]加到dp数组尾部。
反之，说明可以继续优化，显然尾部的元素越小优化的空间就越大，我们利用下界二分查找来进行优化。
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int maxlen = 1e6; int ar[maxlen]; int dp[maxlen]; int main(int argc, char *argv[]) { int n,i,j,k,len,pos; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&ar[i]); len=1; dp[1]=ar[1]; for(i=2;i<=n;i++){ if(ar[i] > dp[len]) dp[++len]=ar[i]; else { pos=lower_bound(dp,dp+len,ar[i])-dp; dp[pos]=ar[i]; } } printf("%d ",len); return 0; }
ModricWang的序列问题II
题面描述：给定一个序列，求出这个序列中的最长上升子序列的长度，且生成的序列中相邻元素的间隔都是不小于T。
这道题在原有题目的基础上增加了长度的限制。
大体解题过程与上一题相同。区别在于对f[]f[] 的操作。没有长度限制的时候，f[]f[] 的更新策略是立即更新。假设间隔为TT，现在由于需要考虑间隔，那么在处理第ii 个元素的时候，就需要看到 前i−Ti−T 个元素生成的f[]f[] ，而不能受到第i−T+1i−T+1 到 i−1i−1 个元素的干扰。因此，考虑如下操作：每次准备更新f[]f[] 时，先不要更新，记录下操作的内容，过TT 步再进行操作，这样就可以让f[]f[] 不再显示当前元素之前TT 步的修改内容，每次更新都不受前TT 步的影响，因此生成的序列中相邻元素的间隔都是不小于TT 的。
详细题解：https://www.cnblogs.com/AlvinZH/p/7978029.html
AlvinZH的最“长”公共子序列
题目描述：给定两个序列，求最少的修改（增加，删除，替换）数，使的两个修改一致。（著名的“编辑距离”问题）
dp[i][j] :记录A的前i个字符与B的前j个字符变成相同需要的最小操作数。
初始化：dp[i][0] = i, dp[0][i] = i。分别代表i次删除or添加操作。
三种操作得到dp[i][j]，取其中最小值:
- 替换：可能不需要替换，所以是dp[i-1][j-1]+Same(A[i-1],B[j-1])；
- 删除：dp[i-1][j]+1；
- 添加：dp[i][j-1]+1。
千万不要纠结操作的序列是A还是B！
初始化：
for (int i = 0; i <= lenA; ++i) dp[i][0] = i;//i次删除操作 for (int i = 0; i <= lenB; ++i) dp[0][i] = i;//i次添加操作
状态转移方程：
for (int i = 1; i <= lenA; ++i) { for (int j = 1; j <= lenB; ++j) { dp[i][j] = MIN(dp[i-1][j-1]+Same(A[i-1],B[j-1]), dp[i-1][j]+1, dp[i][j-1]+1); //MIN(替换, 删除, 添加) } }