线性dp数字三角形,LIS,LCS,LCIS
线性dp(数字三角形，LIS,LCS，LCIS)
线性dp
数字三角形
题目
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
思路
每个数字只能有上方，左上，数字递推而来。最后计算最底层最大值。
int a[1100][1100],f[1100][1100];
void solve()
{
int n;
cin>>n;
fir(i,1,n)
fir(j,1,i)
{
cin>>a[i][j];
}
fir(i,1,n)
{
fir(j,1,i)
f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
}
int mx=0;
fir(i,1,n)
mx=max(f[n][i],mx);
cout<<mx<<'\n';
}那如果向左和向右移动次数相差不能大于1，最大值又是多少了？
易知，当n为偶数，最后一层落在的点一定在n/2或n/2+1.而n为奇数时，最后一层落在的点一定在n/2+1
LIS（最长上升子序列）
例题
数组f【i】，用来存储以a【i】作末尾的上升子序列长度。
代码（n^2）
#include<bits/stdc++.h>
using namespace std;
int a[1000050],f[100050];
int main()
{
int n,ans=1;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
fill(f,f+n+2,1);//初始化
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[j]<a[i])//递增
f[i]=max(f[i],f[j]+1);
}
ans=max(ans,f[i]);
}
cout<<ans<<'\n';
}二分优化（nlogn）
维和一个数组b,存放上升子序列。 其中 b[i]表示长度为 i 的上升子序列的 最小 末尾元素。
从前往后遍历数组a
- a[i]>b[len]末尾元素,b[++len]=a[i]
- a[i]<=b[len],用a[i] 替换b数组第一个>=a[i]的元素
最终b数组的长度便是答案
用vector和lower_bound实现
#include<bits/stdc++.h>
using namespace std;
int n,a[1000050];
int main()
{
cin>>n;
vector<int> d;
for(int i=0;i<n;i++)
{ cin>>a[i];
auto it=lower_bound(d.begin(),d.end(),a[i]);
if(it==d.end())
d.push_back(a[i]);
else *it=a[i];
}
cout<<d.size();
}LCS(最长公共子序列)
这个视频讲的不错 ，本文思路节选于此视频
例题
设
f[i][j]
表示序列
a[1...i]
和
b[1...j]
的最长公共子序列长度。
现在判断末尾元素
a[i]
与
b[j]
是否在公共子序列中：
- 若
a[i] = b[j]：- 则
a[i]与b[j]在公共子序列中。 - 递推关系：
f[i][j] = f[i-1][j-1] + 1
- 则
- 若
a[i] ≠ b[j]，且a[i]不在公共子序列中 ：- 则可去掉
a[i]。 - 递推关系：
f[i][j] = f[i-1][j]
- 则可去掉
- 若
a[i] ≠ b[j]，且b[j]不在公共子序列中 ：- 则可去掉
b[j]。 - 递推关系：
f[i][j] = f[i][j-1]
- 则可去掉
状态转移方程 ：
f [ i ] [ j ]
{ f [ i − 1 ] [ j − 1 ] + 1 , 若 a [ i ]
b [ j ] max ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) , 若 a [ i ] ≠ b [ j ] f[i][j] = \begin{cases} f[i-1][j-1] + 1, & \text{若 } a[i] = b[j] \ \max(f[i-1][j], f[i][j-1]), & \text{若 } a[i] \neq b[j] \end{cases}
f
[
i
]
[
j
]
=
{
f
[
i
−
1
]
[
j
−
1
]
1
,
max
(
f
[
i
−
1
]
[
j
]
,
f
[
i
]
[
j
−
1
])
,
若
a
[
i
]
=
b
[
j
]
若
a
[
i
]
=
b
[
j
]
边界条件 ：
f [ 0 ] [ j ]
0 ; f [ i ] [ 0 ]
0 ; f[0][j]=0;f[i][0]=0;
f
[
0
]
[
j
]
=
0
;
f
[
i
]
[
0
]
=
0
;
代码
int n,f[N][N];
int main()
{ string a,b;
cin>>a>>b;
for(int i=0;i<a.size();i++)
for(int j=0;j<b.size();j++)
{
if(a[i]==b[j])
f[i+1][j+1]=f[i][j]+1;
else
f[i+1][j+1]=max(f[i][j+1],f[i+1][j]);
}
cout<<f[a.size()][b.size()];
}LCS——»LIS
例题
思路
此题特殊之处在于： 全排列
数据范围大，N^2不行
既然两个数组都是1-n的全排列，那么可以用一个新的数组c存放b[i]在数组a中的位置，只有c中递增的子序列才可构成a,b的公共子序列。这样题目就转化为求最长上升子序列了
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],c[N];
int main()
{ cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]=i;//哈希
}
for(int i=1;i<=n;i++)
{ int x;
cin>>x;
c[i]=b[x];//LCS——>LIS
}
vector<int> v;//二分优化的最长上升子序列
for(int i=1;i<=n;i++)
{
auto it=lower_bound(v.begin(),v.end(),c[i]);
if(it==v.end()) v.push_back(c[i]);
else *it=c[i];
}
cout<<v.size();
}最长公共子串
公共子串：字符必须是连续相等的
公共子序列：字符必须是相等的，可以不连续
设
f[i][j]表示序列a[1...i]和b[1...j]的最长公共子串长度。
与最长公共子序列类似，递推公式有所不同。
f [ i ] [ j ]
{ f [ i − 1 ] [ j − 1 ] + 1 , 若 a [ i ]
b [ j ] 0 ， 若 a [ i ] ≠ b [ j ] f[i][j] = \begin{cases} f[i-1][j-1] + 1, & \text{若 } a[i] = b[j] \\ 0， & \text{若 } a[i] \neq b[j]\end{cases}
f
[
i
]
[
j
]
=
{
f
[
i
−
1
]
[
j
−
1
]
1
,
0
，
若
a
[
i
]
=
b
[
j
]
若
a
[
i
]
=
b
[
j
]
最长公共子串不一定是以n,m结尾的，需要比较出最大值。
最长公共上升子序列（LCIS）
这是LIS和LCS的结合。
动态规划状态转移
初始化 ：我们初始化一个二维数组 f，大小为 (n+1) x (n+1)，并将所有元素初始化为 0。这里 n 是序列 A 和 B 的长度。
状态转移 ：
首先判断公共子序列中是否包含a[i]
不包含a [i]的子集，最大值是f[i-1] [j]
包含a[i] 的子集，将这个子集继续划分,依据是子序列的倒数第二个元素在b[]中是哪个数（也就是由谁递推而来）
所以需要一个mx，来记录在当前
i的条件下，满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值。
优化 ：为了提高效率，我们可以在遍历 j 的过程中维护一个最大值 mx，表示在当前 i 的情况下，所有 f [i-1] [k] 的最大值，其中 k < j 且 B[k] < A[i]。这样，我们就可以在 O(1) 的时间更新 f[i][j]。
f[i][j]表示所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的长度最大值。mx用于记录在当前i的条件下，满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值。- 下面代码是一维优化后的代码
int a[3050],b[3050],f[3050];
void solve()
{
int n,mx;
cin>>n;
fir(i,1,n)
cin>>a[i];
fir(i,1,n)
cin>>b[i];
fir(i,1,n)//只看前i个
{
mx=1;
fir(j,1,n)
{
if(a[i]==b[j]) f[j]=max(f[j],mx);
if(a[i]>b[j]) mx=max(mx,f[j]+1);
}
}
mx=0;
fir(i,1,n)
mx=max(f[i],mx);
cout<<mx<<'\n';
}