hiho一下第201周《Composition》题目分析

8
4

《Composition》题目分析

本题最暴力的解法就是枚举哪些字符被删掉。枚举的复杂度是O(2^N),再加上O(N)的判断,总复杂度是O(N2^N)。

比较容易想到的是O(N^2)的DP。

由于删掉最少等价于留下最多,所以我们可以用f[i]表示最后留下一个字符是S[i]时,最多留下多少个字符。

要求f[i],我们只需要枚举S[i]之前的一个字符是哪个,并且从中选择合法并且最优的解:

f[i] = max{f[j]} + 1, for j = 1 .. i-1且S[j]S[i]不是"illegal pair"。

以上的DP解法是O(N^2)的,仍有优化的空间。

我们求f[i]时,需要枚举之前所有的位置j,但实际上之前的字符只有'a'~'z'26种可能。对于相同的字符,我们只用考虑最后一次它出现的位置,之前的位置一定不是最优。

例如,假设s[2] = s[5] = s[8] = 'h',那么当i>8时,我们求f[i]根本不用考虑j=2和j=5的情况,这两种情况即便合法也不会比j=8更优。

于是我们每次求f[i]只需要考虑'a'~'z'最后一次出现的位置。复杂度可以优化到O(26N)。

write answer 切换为英文 切换为中文


转发分享