时间戳

首页 > 解决方案 > 通过从侧面或中间删除来创建“A”字符串的最低成本

algorithm - 通过从侧面或中间删除来创建“A”字符串的最低成本

问题描述

假设我有一串 A 和 B。我可以以 1 的成本从字符串的任一端移除一个字符，或者我可以以 2 的成本从中间移除任何字符。创建一个只有 A 的字符串的最低成本是多少？

例如，如果我有字符串“BBABAA”，那么要删除的最小成本是 4，因为我会以 2 的成本从左​​侧移除 B，然后以 2 的成本从右侧移除单数 B，导致总成本为 4。

我尝试了一个自上而下的缓存解决方案：

def MRC_helper(s, count, cache):
    if count == 0:
        cache[s] = 0
        cache[s[::-1]] = 0
        return 0
    if s in cache:
        return cache[s]

    min_cost = len(s)
    for i in range(len(s)):
        new_count = count - int(s[i] == 'B')
        new_s = s[:i]+s[i+1:]
        if i == 0 or i == len(s)-1:
            min_cost = min(min_cost, 1 + MRC_helper(new_s, new_count, cache))
        elif s[i] == 'B':
            min_cost = min(min_cost, 2 + MRC_helper(new_s, new_count, cache))

    cache[s] = min_cost
    cache[s[::-1]] = min_cost
    return min_cost

def minRemovalCost(s):
    min_cost = MRC_helper(s, s.count('B'), {})
    return min_cost

这个想法非常简单：对于可以删除的每个字符，尝试将其删除并计算转换结果子字符串的成本。然后计算最小成本移动并缓存它。我还向前和向后缓存字符串，因为它是同一件事。我的朋友说可以贪婪地做，但我不同意。任何人都可以阐明比我更好的解决方案吗？

标签： algorithm

解决方案

B必须删除所有s。如果我们B从中间删除一个，我们将字符串分成两部分。对于右侧的部分，不能从左侧删除任何字符，否则我们会B以较低的删除成本从左侧删除。左侧部分的镜子。不能从一侧删除的部分可以通过从允许删除的一侧迭代并在每个点比较该删除与中间删除的成本来解决。预先计算后者并在最佳中间相遇。

Example 1:

            BBABAA
              x
cost_l: --> 122444
cost_r:     642200 <--
               x
               
optimal:     22    = 4
              22   = 4
               40  = 4
                40 = 4
                 4 = 4

Example 2:

            ABBA
              x
cost_l: --> 0233
cost_r:     3320 <--
               x
               
optimal:       3 = 3
              30 = 3
            03   = 3
            3    = 3

如果不清楚，单方面的成本计算是：

cost_l(0) ->
  0 if str[0] == 'A' else 1

cost_l(i) ->
  if str[i] == 'B':
    min(2 + cost_l(i-1), i + 1)
  else:
    cost_l(i - 1)

（镜像cost_r。）

推荐阅读