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];
}
例题
由"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;