线性DP总结（LIS,LCS,LCIS，最长子段和）
线性DP总结（LIS,LCS,LCIS，最长子段和）
做了一段时间的线性dp的题目是时候做一个总结 线性动态规划无非就是在一个数组上搞嘛， 首先看一个最简单的问题： 一，最长字段和 下面为状态转移方程
for(int i=2;i<=n;i++)
{
if(dp[i-1]>=0)
dp[i]=dp[i-1]+a[i];
else
dp[i]=a[i];
}例题 裸的最长字段和 可以用滚动数组，下面是用滚动数组写的
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdlib.h>
using namespace std;
int n;
int a;
int sum;
int _begin;
int _end;
int main()
{
int t;
scanf("%d",&t);
int k=0;
while(t--)
{
int max;
int x=1;
scanf("%d%d",&n,&a);
sum=a;
max=a;
_begin=_end=1;
for(int i=2;i<=n;i++)
{
scanf("%d",&a);
if(sum>=0)
{
sum+=a;
}
else
{
sum=a;
x=i;
}
if(max<sum)
{
max=sum;
_begin=x;
_end=i;
}
}
cout<<"Case "<<++k<<":"<<endl<<max<<" "<<_begin<<" "<<_end<<endl;
if(t)
cout<<endl;
}
return 0;
}升级一下，二维的呢？也就是求最大子矩阵和 状态转移方程，其实就是将一维转换成二维的，如何转换呢？操作就是将第一行每个数加上第二行对应的每个数，变成一维的进行dp,再加上第三行对应的每个数，进行DP。起点行分别枚举从1到n。
for(int i=1;i<=n;i++)
{
memset(b,0,sizeof(b));
memset(dp,0,sizeof(dp));
for(int k=i;k<=n;k++)
{
for(int j=1;j<=n;j++)
{
b[j]+=a[k][j];
if(dp[j-1]>=0)
dp[j]=dp[j-1]+b[j];
else
dp[j]=b[j];
if(sum<dp[j])
sum=dp[j];
}
}
}#include <iostream>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int a[105][105];
int n;
int dp[105];
int b[105];
int sum;
int main()
{
while(scanf("%d",&n)!=EOF)
{
sum=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++)
{
memset(b,0,sizeof(b));
memset(dp,0,sizeof(dp));
for(int k=i;k<=n;k++)
{
for(int j=1;j<=n;j++)
{
b[j]+=a[k][j];
if(dp[j-1]>=0)
dp[j]=dp[j-1]+b[j];
else
dp[j]=b[j];
if(sum<dp[j])
sum=dp[j];
}
}
}
printf("%d\n",sum);
}
return 0;
}接下来就是LIS问题，LIS就是最长下降子序列或者是最长上升子序列。有O(n^2)效率的算法，也有O(nlogn)效率的算法。 先说O(n^2)效率的算法。很简单，DP[j] = MAX(DP[i]) + 1 满足条件a[j] > a[i] 转态转移方程
for(int i=2;i<=n+1;i++)
{
int num=0;
for(int j=i-1;j>=1;j--)
{
if(a[i]>a[j])
num=max(num,dp[j]);
}
dp[i]=num+1;
}O(nlogn)效率的算法，参考这篇博文 博文 其实过程很简单，以最长上升子序列为例。dp数组的最终长度就是最长上升子序列，遍历a数组，a[i]如果比dp数组最后一个元素大，即a[i]>dp[len]则直接加入dp数组里。否则就要二分查找到第一个小于a[i]的dp[j],然后将dp[j]换成a[i],最终的dp数组的长度就是答案。 例题
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
#define MAX 40000
int a[MAX+5];
int dp[MAX+5];
int n;
int search(int num,int l,int r)
{
int mid;
while(l<=r)
{
mid=(l+r)/2;
if(num>=dp[mid])
l=mid+1;
else
r=mid-1;
}
return l;
}
int main()
{
int cas=0;
int x,y;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
memset(dp,0,sizeof(dp));
dp[1]=a[1];
int len=1;
for(int i=2;i<=n;i++)
{
if(a[i]>=dp[len])
dp[++len]=a[i];
else
{
int pos=search(a[i],1,len);
dp[pos]=a[i];
}
}
printf("%d\n",len);
}
return 0;
}还有一个比较相似的求最长连续上升子序列或最长连续下降子序列。求解这个就不用DP了，应该用线段树。
接下来就是LCS,最长公共子序列问题，这个也有O(n^2)的效率和O(nlogn)的效率 O(n^2)效率的看代码
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
if(s1[i]==s2[j])
dp[i+1][j+1]=dp[i][j]+1;
else
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
}
}O(nlogn)效率是把LCS转化成LIS问题 a[] = {a, b, c,} b[] = {a,b,c,b,a,d},那么a中的a，b，c在b中出现的位置分别就是{0,4},{1,3},{2}分别按降序排列后代入a序列就是{4,0,2,3,1}，