动态规划之滚动数组和枚举顺序

113 阅读 0 评论 75 点赞

我是靠谱客的博主精明钻石，这篇文章主要介绍动态规划之滚动数组和枚举顺序，现在分享给大家，希望可以做个参考。

简单题：给定两个字符串 $s1$ ， $s2$ ，长度分别为 $l1$ ， $l2$ ，求它们的最长公共子串。

这是一道经典的 $dp$ 水题，设 $dp[i][j]$ 表示以 $s1[i]$ ， $s2[j]$ 结尾的最长公共子串的长度，代码如下。

复制代码

1
2
3
4
5
6
7
8
int dp[maxn][maxn];
for(int i=1;i<=l1;i++)
	for(int j=1;j<=l2;j++)
	if(s1[i]==s2[j])
	{
		dp[i][j]=dp[i-1][j-1]+1;
		if(dp[i][j]>ans) ans=dp[i][j];
	}

$O(n^2)$ 的时间复杂度还是可以接受的，但当串长较大时， $O(n^2)$ 的空间复杂度往往会导致 $MLE$ ，因此我们考虑使用滚动数组。我们发现，对于每个 $i$ ， $dp[i][]$ 只由 $dp[i-1][]$ 转移而来，绝大部分数组在统计答案后就不再参与计算，十分浪费空间。考虑到每次参与递推的只有两行，我们可以只开一个两行的数组，让它们交替使用，代码如下。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int dp[2][maxn];
for(int i=1;i<=l1;i++)
	for(int j=1;j<=l2;j++)
		if(i%2)
		{
			if(s1[i]==s2[j])
			{
				dp[1][j]=dp[0][j-1]+1;
				if(dp[1][j]>ans) ans=dp[1][j];
			}
			else dp[1][j]=0;
		}
		else
		{
			if(s1[i]==s2[j])
			{
				dp[0][j]=dp[1][j-1]+1;
				if(dp[0][j]>ans) ans=dp[0][j];
			}
			else dp[0][j]=0;
		}

$O(2*n)$ 的空间复杂度足以通过本题，那我们能否只开一维数组，把空间复杂度再降到一半呢？其实是可以的，但要在循环的顺序上做文章，代码如下。

复制代码

1
2
3
4
5
6
7
8
9
10
11
int dp[maxn];
for(int i=1;i<=l1;i++)
	for(int j=l2;j;j--)
	{
		if(s1[i]==s2[j])
		{
			dp[j]=dp[j-1]+1;
			if(dp[j]>ans) ans=dp[j];
		}
		else dp[j]=0;
	}

当开 $maxn$ 行或 $2$ 行的数组时， $j$ 的枚举顺序无关紧要，因为同一行的结果不会互相冲突，但在只有 $1$ 行的情况下， $j$ 的枚举顺序就变得至关重要，因为被强行压掉了一维，转移方程变为 $dp[j]=dp[j-1]+1$ ，每一行的结果一算出来，就会被下一行覆盖。如果正序枚举 $j$ ， $dp[j]$ 还没算出来， $dp[j-1]$ 就会被覆盖，得不到正确的 $dp[j]$ ，因此，我们需要逆序枚举 $j$ 。

$LCIS$ ：https://www.cnblogs.com/gj-Acit/p/3236384.html

这篇文章写得不错，没我什么事了。 $LCIS$ 的状态 $dp[i][j]$ 表示以 $s1[1-i]$ ， $s2[1-j]$ 可以构成且以 $s2[j]$ 结尾的 $LCIS$ 的长度，状态的定义要特别注意，否则会与 $LCS$ 的转移方程 $dp[i][j]=max(dp[i-1][j],dp[i][j-1])$ 搞混。