动态规划基础

参考资料

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

最长上升子序列

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

朴素 DP 设 $f_i$ 为以 $a_i$ 结尾的 LIS 长度，由所有满足 $a_j<a_i$ 的 $f_j$ 转移，复杂度 $O(n^2)$。用一个单调数组配合二分（维护各长度 LIS 的最小结尾），或用树状数组维护前缀最大值，都能优化到 $O(n\log n)$。

动态规划

120 Bcpp

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]);
}

二分查找

92 Bcpp

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);
}

树状数组

83 Bcpp

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

例题

洛谷 B3637 最长上升子序列

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

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

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

69 Btext

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

洛谷 P2758 编辑距离

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

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