在leetcode面经上发现一道有意思的题目，大家可以一起讨论一下

这个问题可以用两阶段的动态规划做吧，时间是O(n^3)，不知道可不可以进一步优化了

--
首先我们定义一个数组A可以被“全消除”，记作 IsFullyCrushable(A)，当且仅当存在一个消除过程，使得A中的所有元素最后都被消除掉。

然后，给定输入数组S，定义可以全消除的区间集合：I = { [i, j] | IsFullyCrushable( S[i..j] ) }

也就是说I是S中可以被全消除的所有子串的区间集合，易知I中的区间数量不超过 n^2

举个例子，对于 S = 322233322，可以被全消除的子串有：
(1) 区间 [1, 3]: .222.....
(2) 区间 [4, 6]: ....333..
(3) 区间 [0, 5]: 322233...
(4) 区间 [0, 6]: 3222333..
(5) 区间 [1, 6]: .222333..
(6) 区间 [1, 7]: .2223332.
(7) 区间 [1, 8]: .22233322
(8) 区间 [2, 8]: ..2233322
(9) 区间 [3, 8]: ...233322

那么对应的 I 就是上面9个区间的集合。

然后我们有如下关键性质：

定理(a)：给定数组S，通过一系列消除过程可以消除的最大长度K，等于I中互不相交的区间子集的最大总长度

还是上面的例子，那么最大的互不相交区间集合总长度是K = 8（这个例子里最优解只有一个元素[1, 8]，但是把输入弄复杂一点的话最优解就会是多个区间组成的集合了）

然后原题要计算的是最短剩余长度，那么返回 len(S) - K 即可。


所以接下来需要进一步回答三个问题：
--
1. 定理(a)如何证明？

定理(a)本身可以通过考察消除过程来证明，这里略过..

--
2. 给定I，如何求I中互不相交区间子集的最大总长度？

本质上是一个weighted interval scheduling problem，可以先排序，再DP，参考这里：https://courses.cs.washington.ed ... ides/06dp-sched.pdf

时间复杂度由排序时间决定，因为I中元素数量不超过n^2，所以就是 O(n^2 * log(n))

--
3. 如何计算得到集合 I ？

为了简洁，记 C(i, j) = IsFullyCrushable( S[i..j] )，那么对于所有区间[i, j]，计算C(i, j)并将值为"true"的区间加入I即可。

现在我们要写出C(i, j)的状态转移方程，那么就是C(i, j)值为true，当且仅当下面任一条件被满足：
(1) S[i..j]全部为同一字符且长度大于等于3
(2) 存在i < k < j，使得 C(i, k)为true 且 C(k + 1, j)为true
(3) 存在i < m < n < j，使得C(m, n)为true 且 S[i..m-1]并上S[n+1,j]全部为同一字符且长度大于等于3

这个状态转移方程的时间复杂度主要在(2)需要枚举所有k，综合起来就是 O(n^3)

注意到对于(3)式我们不需要枚举所有m，n，只要同时从左从右贪最多的同一字符然后检查即可，其正确性可以用数学归纳法证明


补充内容 (2019-6-16 03:09):
谢谢zjck1995指出来计算I时没有考虑到 5 1 1 1 5 1 1 1 5 这种情况，处理方法可以引入一个新函数H(i, j)表示消除后可以得到的最多"i位置上的字符"个数，然后式子(3)改为 H(i, j) >= 3，具体可以看下面帖子的讨论

补充内容 (2019-6-16 14:34):
写了一份参考代码：http://cpp.sh/3jcqk

蹲一下这个题………………

插个眼 等一个优化

magicsets 发表于 2019-6-15 12:40
这个问题可以用两阶段的动态规划做吧，时间是O(n^3)，不知道可不可以进一步优化了

--

请问下对于C(i, j)，如果是这种情况呢：
5 1 1 1 5 1 1 1 5
要怎么计算C(0, 8)

谢谢楼主分享！

谢谢楼主分享！

这题的确没有什么想法！

zjck1995 发表于 2019-6-15 22:07
请问下对于C(i, j)，如果是这种情况呢：
5 1 1 1 5 1 1 1 5
要怎么计算C(0, 8)

这种情况之前确实没有考虑.. 要解决的话可以再加一个状态函数：

给定输入数组S，定义 H(i, j) 取值如下：

(1)
如果S[i] != S[j]，那么 H(i, j) = 0

(2)
否则S[i] == S[j]，不妨设该字符为X

那么S[i..j]必然是如下形式：X...X...XX.....X，也就是说两端是X，然后中间夹了任意多个X

那么我们定义H(i, j)为经过任意消除过程后可以得到的最长的"全X" 串的长度；如果不能消除到只剩下X，那么取值0

比如511151115，对应的H(0, 0) = 1, H(0, 1) = 0, H(0, 4) = 2，H(4, 8) = 2，H(0, 8) = 3，等等

--
现在将C(i, j)为true的第(3)个条件改为 H(i, j) >= 3

最后可以写出H(i, j)的状态转移方程

H(i, j) = max{ H(i, k) + H(k, j) - 1 | 对于所有 i < k < j 如果 S[i] == S[k] == S[j] 并且 C(i + 1, k - 1)为true 且C(k + 1, j - 1)为true }

注意i == j以及i + 1 == j的边界条件要额外处理一下，然后另一个边界条件是令 C(a, b) = true如果a的值大于b的话

可以看出H函数与C函数互相依赖，但本质上是stratified recursion（也就是不存在循环依赖），综合起来还是O(n^3)的时间

补充内容 (2019-6-16 02:59):
帖子里的 [ i ] 被吞掉了，一开始的两段话是 “如果S[ i ] != S[j] ... ” 以及 “否则S[ i ] == S[j] ...”

补充内容 (2019-6-16 03:13):
然后H(i, j)还有一个边界情况是除了两端之外中间没有任何X，上面的状态转移方程没有Cover到，单独处理一下即可

补充内容 (2019-6-16 14:33):
又看了一下上面H(i, j)的状态转移方程还是不太对.. 不需要满足条件C(i + 1, k - 1)以及C(k + 1, j - 1)，而是直接算最大值即可，并需要使用一个"INVALID‘值（比如-1）来标记无法消除到只剩X字符的情况

补充内容 (2019-6-16 14:34):
写了一份代码用于测试.. http://cpp.sh/3jcqk

所有说o(n)的请用你的算法测试一下aaabbbabbba这个testcase

zjck1995 发表于 2019/06/14 22:35:51
FYI:  https://codeforces.com/blog/entry/67618

cf 3500 的大佬都没做出来....我觉得作为面试题八成是缺少某种约束条件