题目描述

小美有一个数字串$x$，她将$x$的所有非空子序列都取了出来，将其中满足相邻数位两两不同的子序列都加入了集合$S$ 中。

题目思路

考虑dp，设f[i][c]表示前i个字符组成的以c为结尾的合法子序列个数。

假设当前位为j，由于要去重，前面所有以j结尾的子序列对于当前位来说同样可以构造，所以只需要考虑前一位不是以j结尾的答案，同时注意当前这一位可以单独放一个算子序列，所以加上1。

所以转移方程f[i][j] = sum(f[i]) - f[i - 1][j] + 1，最后统计sum(f[n - 1])即可。

由于dp转移只需要考虑前一位，所以可以优化空间复杂度为O(1)。