假设我有一个由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
这个想法很简单：对于每个可以删除的字符，尝试删除它，并计算转换生成的子字符串的成本。然后计算最小成本移动并缓存它。我也向前和向后缓存字符串，因为这是一样的。我的朋友说可以贪婪地做，但我不同意。有谁能为比我更好的解决方案提供一些线索吗？
必须删除所有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的镜像。)
设C是一个数组，其中C[i]是子串s[0:i+1]的最优开销(假设右sise是独占的)。
考虑另一个游戏，完全相同，只是从正确的角度吃东西的成本是2而不是1。让D是这个新游戏的相关成本数组，这个成本有助于跟踪我们限制自己不吃子串的最后一个元素的情况。
我们在单程循环中计算C和D，如下所示：由第一个字符组成的减法的最佳成本值为：
C[0] = int(s1=='B' )# (1 if It Is B, 0 otherwise)
D[0] = int( s1=='B')
对于i+1，如果我们吃掉最后一个字符，成本为1+C[i](如果是"B"，我们必须吃掉最后一个字符)如果我们不吃掉最后一个字符，成本等于D[i]，因为我们不能从右边吃东西。所以
C[i+1]=C[i]+1 if s[i+1]=='B' else min(C[i]+1,D[i])
同样，对于第二个游戏，如果我们吃了最后一个角色，那么我们要么从右边吃2个，要么我们也必须吃左边的所有东西。所以
D[i+1]=min(D[i]+2, i+1) if s[i+1]=='B' else D[i].
因此，我们对i进行迭代，并输出C[len(s)]。这在时间和内存上是O(len(s))，尽管如果我们只保留上一次迭代的成本，它在内存中会变为常数(不推荐，因为我们无法再通过回溯恢复最佳策略)。
int n = s.length();
int l[] = new int[];
int r[] = new int[];
if(s.charAt(0)=='b') l[0]=1;
if(s.charAt(n-1)=='b') r[n-1]=1;
for(int i = 1; i<n; i++) {
l[i] = Math.min(l[i-1]+2, i+1);
}
for(int i = n-2; i>=0; i--) {
r[i] = Math.min(r[i+1]+2, n-i);
}
int ans = Math.min(l[n-1], r[0]);
for(int i = 0; i<n-1; i++) {
ans = Math.min(l[i] + r[i+1]);
}
return ans;