不同形态的子序列的方案

catalog

问题

给定一个长度n=1e6的字符串,其中有x种 不同的字符。 求有多少种 不同的 非空子序列

"abc": a, b, c, ab, ac, bc, abc

问题倒是很简单,显然我们2 ^ n遍历所有子序列,然后放到一个set里 去重,这就是答案。


因为涉及到“去重”,看似是与dp无关…
但这个时间复杂度,可以尝试下dp。

首先,我们将问题简化,比如x=2,字符串里只有a和b

定义dp[i][0]: 前i个字符中,选择以’a’为结尾字符的 子序列(这个’a’,不一定是[i],即dp[i][x]里的方案 不一定是以[i]结尾的)

答案即为: dp[n][0] + dp[n][1]

比如: 当前位[i] 是 a
则,dp[i][b] = dp[i - 1][b] (结尾是b的,直接继承 这是肯定的,因为当前位是a)
关键是求: dp[i][a]

根据dp的定义,dp[i][a]可以分为2种: 
	A =  以[i]字符为结尾(自然结尾字符是a)的 子序列。
	B = 不以[i]字符为结尾(且结尾字符是a)的 子序列。
' 这一步分析非常重要!!! 因为这完全是根据dp原理进行的 '
	
A =   dp[i - 1][a]  +  dp[i - 1][b]   +   1
		  X类				Y类			 Z类    	
B =   dp[i - 1][a]

X类是: 倒数第2字符是a,倒数第1字符是[i]=a
Y类是: 倒数第2字符是b,倒数第1字符是[i]=a
Z类是: 没有倒数第2字符,子序列长度是1,即只有一个字符[i]=a

首先,先不要考虑: A 和 B 中,有重复形态的子序列 这个问题。

要关注的是,反正根据dp定义,就得到了这样的dp转换。
也就是:  ' 当前需要求的dp[i][a] 所代表的 所有形态子序列 '
		 ' 他一定被包含在:  A + B 的所有形态子序列 '
而且,A内部没有重复形态、B内部也没有重复形态!!!

即,A 和 B 所存在的重复形态,一定是: 一个在A里,另一个在B里
比如:  B里有个"aa",A里也有个"aa"

即,dp[i][a] = A + B - same     ' same为:AB集合里,重复形态的个数 '

由于,A中的 X类 他的个数 = B。  即,A >= B
' X类 和 B,只是个数相同。但形态不一定完全相同,形态是未知的 '

B集合很小,我们重心看B 中 有多少个same

考虑,B 有哪些“可能”的形态
(再强调下B的定义: 在[..., i-1]中 以a为结尾的子序列,即是没有当前[i]元素的 )
(A类是: 一定以[i]=a为结尾的子序列!)
a:     我们知道,A中的 Z类,也有一个a
aa:	这个"aa"中的一个a,可以和[i] 同样组成"aa"。即A中的 X类,也有个"aa"
ba:	这个"ba"中的b,可以和[i] 同样组成"ba"。即A中的 Y类,也有个"ba"
aaa:   这个"aaa"中的aa,可以和[i] 同样组成"aaa"。即A中的 X类,也有个"aaa"
bba:   这个"bba"中的bb,可以和[i] 同样组成"bba"。即A中的 Y类,也有个"bba"
aba:   这个"aba"中的ab,可以和[i] 同样组成"aba"。即A中的 Y类,也有个"aba"
baa:   这个"baa"中的ba,可以和[i] 同样组成"baa"。即A中的 X类,也有个"baa"

' 即,B中所有的形态,都已经存在于A中。 same = B !! '

比如举个例子:
a b a a [a]

A中的X类有: aa, aaa, baa, abaa, aaaa, baaa, abaaa
A中的Y类有: ba, aba
A中的Z类有: a
 ' A中的 所有最后的a,都是[i] '

B有: a, aa, aba, ba, abaa, aaa, baa  (可以发现,他们在A中的 XYZ里,都有!!)

模板

长度n=1e6,仅由ab组成的字符串, 所有非空 子序列形态。

int dp[n][2];

dp[0][ s[0] - 'a' ] = 1;

FOR(i, 1, n-1, 1){
	int cur = s[i] - 'a';
	
	FOR(j, 0, 1, 1){
		if( j == cur ){
			dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + 1;
		}else{
			dp[i][j] = dp[i - 1][j];
		}
	}
}
DE<< dp[n-1][0] + dp[n-1][1]; ED;

代码非常短,但思路确实很难!!!
而且,与以往dp非常不同的是: 这个dp转移方程dp[i][j] = dp[i-1][0] + dp[i-1][1] + 1 并不是能 直接通过原问题而得到的!!
他是通过: 从dp定义出发,然后通过 证明 才能得到,并不是直接从原问题就能推导出。

因为,如果直接看这个转移方程: 即dp[i][a]为: 以[i]=a为结尾 的方案。
但dp[i][a]定义的是: 不一定以[i]结尾。所以,和以往dp不同,这并不是直接从原问题就能得出的!
但,通过证明,这个方程确实是这样。


推广到有x个字符:abcde....,也是一样的。

int dp[n][x];

dp[0][ s[0] - 'a' ] = 1;

FOR(i, 1, n-1, 1){
	int cur = s[i] - 'a';
	
	FOR(j, 0, x-1, 1){
		if( j == cur ){
			dp[i][j] = 1;
			FOR(z, 0, x-1, 1) dp[i][j] += dp[i - 1][z];
		}else{
			dp[i][j] = dp[i - 1][j];
		}
	}
}

FOR(j, 0, x-1, 1){
	ans += dp[n - 1][j];
}

例题

LINK

由"01"组成,且不能有前导零。 (但单独的0可以)

"101" -> 0, 1, 10, 11, 101

先求所有: “不带前导零的”(0也算是有前导零)
然后,最后找原串中 是否有0,再 + 1

if( s[0] == '1' ) dp[0][1] = 1;

FOR(i, 1, n-1, 1){
	if( s[i] == '1' ){
		dp[i][0] = dp[i - 1][0];
		dp[i][1] = dp[i - 1][0] + dp[i - 1][1] + 1;
	}else{
		' 这里是重点! 那个+1,表示是单独的一个0。 不+1,这样就不含有前导零了 '
		dp[i][0] = dp[i - 1][0] + dp[i - 1][1];	
		dp[i][1] = dp[i - 1][1];
	}
}

bool findd = ( s.find('0') != -1 );

return dp[n-1][0] + dp[n-1][1] + findd;
上一篇:Markdown语法


下一篇:测绘线性代数(五):快速求解伪逆