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

53 阅读 0 评论 35 点赞

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

概述

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

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

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][]$ 转移而来，绝大部分数组在统计答案后就不再参与计算，十分浪费空间。考虑到每次参与递推的只有两行，我们可以只开一个两行的数组，让它们交替使用，代码如下。

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

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])$ 搞混。