动态规划基础

参考资料

• 动态规划基础 - OI Wiki
• 最长递增子序列 - 维基百科

最长上升子序列（LIS）

最长上升子序列：找到给定序列的一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能大。

动态规划

for(int i=1;i<=n;i++)
{
    f[i]=1;
    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]);
}

二分查找

for(int i=1;i<=n;i++)
{
    int k=lower_bound(b+1,b+n+1,a[i])-b;
    b[k]=a[i];
    ans=max(ans,k);
}

树状数组

for(int i=1;i<=n;i++)
{
    int k=query(a[i]-1)+1;
    update(a[i],k);
    ans=max(ans,k);
}

例题

洛谷 B3637 最长上升子序列

洛谷 B3637 最长上升子序列

给定一个长度为 $n$ 的正整数序列 $a_i$，求最长上升子序列的长度。（$n\le5000,a_i\le10^6$）

Reference Code (3)

二分查找

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=5005;
int a[N],b[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)b[i]=inf;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int k=lower_bound(b+1,b+n+1,a[i])-b;
		b[k]=a[i];
		ans=max(ans,k);
	}
	cout<<ans<<'\n';
	return 0;
}

动态规划

#include <bits/stdc++.h>
using namespace std;

const int N=5005;
int a[N],f[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		f[i]=1;
		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';
	return 0;
}

树状数组

#include <bits/stdc++.h>
using namespace std;

const int N=1000005;
int a[N],c[N];
void update(int u,int v)
{
	while(u<N)
	{
		c[u]=max(c[u],v);
		u+=u&-u;
	}
}
int query(int u)
{
	int res=0;
	while(u)
	{
		res=max(res,c[u]);
		u-=u&-u;
	}
	return res;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int k=query(a[i]-1)+1;
		update(a[i],k);
		ans=max(ans,k);
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P1216 [IOI 1994] 数字三角形 Number Triangles

洛谷 P1216 [IOI 1994] 数字三角形 Number Triangles

给定一个 $r$ 行的数字三角形（$r \leq 1000$），需要找到一条从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到当前点左下方的点或右下方的点。在下面这个例子中，最优路径是 $7 \to 3 \to 8 \to 7 \to 5$。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

Reference Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
int a[N][N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=n-1;i>=1;i--)
	{
		for(int j=1;j<=i;j++)
		{
			a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
		}
	}
	cout<<a[1][1]<<'\n';
	return 0;
}

洛谷 P2758 编辑距离

洛谷 P2758 编辑距离

设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

Reference Code (1)

#include <bits/stdc++.h>
using namespace std;

const int N=2005;
int f[N][N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string a,b;
	cin>>a>>b;
	int n=a.size(),m=b.size();
	for(int i=0;i<=n;i++)f[i][0]=i;
	for(int j=0;j<=m;j++)f[0][j]=j;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i-1]==b[j-1])f[i][j]=f[i-1][j-1];
			else f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
		}
	}
	cout<<f[n][m]<<'\n';
	return 0;
}