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

Question

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

例如，如果我有字符串“BBABAA”，那么删除的最小成本是 4，因为我会以 2 的成本从左​​侧删除 B，然后以 1 的成本从右侧删除单数 B 2，导致合并成本为 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

这个想法非常简单:对于您可以删除的每个字符，尝试删除它并计算转换生成的子字符串的成本。然后计算最小成本移动并缓存它。我还向前和向后缓存字符串，因为它是同一件事。 friend 说可以贪心做，我不同意。有人能阐明比我更好的解决方案吗？

Answer 1

必须删除所有 B。如果我们从中间删除一个 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 的镜像。)