移除全同字符子串最大化总得分的多项式时间算法优化咨询
原来的记忆化方案核心缺陷是把可变字符串作为状态存储,枚举所有可能的删除序列对应的剩余串,状态数随字符串长度呈指数级增长,n=20时就会产生上百万个状态,自然无法处理更长的输入。完全可以通过绑定原始位置的区间DP思路,将时间复杂度降到O(N³),足够处理数百长度的输入。
第一步:预计算同字符串的最大拆分项
所有同字符串无论怎么拆分移除,最终的最大得分只和它的总长度有关,和位置无关。我们可以先在O(N²)时间内预计算数组best:
best[k]表示:把长度为k的连续全相同字符串,拆成任意多段依次移除,能拿到的最高得分。- 递推关系:
- 边界:
best[0] = 0 - 对每个长度
k(从1到N),枚举最后一次移除的子串长度t(从1到k),则best[k] = max( A[t-1] + best[k-t] )
- 边界:
对应题目给出的例子,当A=[2,3,1]时,计算得到的best数组为:
best[1] = 2(长度1得2分)best[2] = max(2+2, 3) =4(拆成两个长度1移,得4分,比整段移的3分高)best[3] = max(2+4, 3+2, 1) =6
完全匹配题目给出的最优得分情况。
第二步:游程编码压缩原始字符串
原始字符串里连续相同的字符本质上是一个整体块,完全可以先压缩成块列表blocks,每个块记录两个属性:字符值c、块的原始长度len。比如原串"xyy"压缩后得到两个块:[('x',1), ('y',2)]。
这一步可以把块的总数m压缩到小于等于原串长度N,相邻块的字符一定不同。
第三步:定义区间DP状态
因为移除操作会把夹在同字符块之间的异字符块删掉,最终让两边的同字符块合并,我们定义状态:dp[l][r][k]:表示处理完块列表中下标从l到r的所有块,并且在第r个块的右侧,还额外连着k个和r块字符相同的字符(这些字符是之前删除中间块后合并过来的)时,能获得的最大总分。
- 边界条件:当
l > r(区间内没有块),dp[l][r][k] = 0;当l == r(区间内只有一个块),直接返回best[ blocks[l].len +k ]即可,因为整个区间是同字符。
第四步:状态转移
对每个状态dp[l][r][k],有两种最优的拆分选择:
- 先把第
r个块和右侧连着的k个同字符合并成一个整体,用预计算好的best算出这部分的最大得分,剩下的就是处理完l到r-1的块(此时右侧没有连着的同字符),对应得分:dp[l][r-1][0] + best[ blocks[r].len +k ] - 不提前拆
r块和右侧的连块,而是在l到r-1的范围内,找所有和r块字符相同的位置p:先把p+1到r-1的块全部拆完,这样p块就会和r块、右侧的k个同字符彻底连通合并;此时的总得分就是:dp[l][p][ blocks[r].len +k ] + dp[p+1][r-1][0]
取所有可选转移的最大值,就是当前状态的最优解。
复杂度说明
块总数m最多等于原串长度N,连块长度k最多等于原串总长度N,枚举拆分位置p的范围最多是m,整体时间复杂度为O(N³),和经典的移除盒子问题复杂度一致,完全可以支撑长度达到1000量级的输入,远强于原来指数级的记忆化方案。
针对题目给出的S="xyy"、A=[2,3,1]的例子,我们最终求解的目标是
dp[0][1][0],计算过程得到的结果为6,和题目给出的最优方案得分完全一致。
内容的提问来源于stack exchange,提问作者Mukul Bindal

