在Python中查找最少删除成本以避免重复字符的程序

假设我们有一个字符串s和一个叫做cost的整数数组，其中cost[i]表示删除s中第i个字符的成本。我们必须找到最小的删除成本，这样在任意两个相同的字母之间都没有相同的字母。我们必须注意，我们将同时删除所选字符。因此，在删除一个字符之后，删除其他字符的成本将不会改变。

因此，如果输入是s =“pptpp”，cost = [2,3,4,5,2]，则输出将是4，因为如果我们用成本2 + 2 = 4删除第一个和最后一个p，则字符串将是“ptp”，这里没有相同的字符是相邻的。

要解决这个问题，我们将采取以下步骤−

cost_f := 0
i := 1
ind := 0
for i in range 1 to size of s – 1, do
- cur := s[i], c_cost := cost[i]
- prev := s[i-1], p_cost := cost[i-1]
- if ind is same as 1, then
  - prev := prev_i, p_cost := cost_i
- if cur is same as prev, then
  - if c_cost >= p_cost, then
  - cost_f := cost_f + p_cost
  - prev_i := 0, cost_i := 0
  - ind := 0
  - if c_cost < p_cost, then
  - cost_f := cost_f + c_cost
  - ind := 1
  - prev_i := prev, cost_i := p_cost
- otherwise,
  - prev_i := 0, cost_i := 0
  - ind := 0
return cost_f

例如

让我们看下面的实现，以便更好地理解：

def solve(s, cost):
   cost_f = 0
   i = 1
   ind = 0

   for i in range(1, len(s)):
      cur, c_cost = s[i], cost[i]
      prev, p_cost = s[i-1], cost[i-1]
      if ind == 1:
         prev, p_cost = prev_i, cost_i

      if cur == prev:
         if c_cost >= p_cost:
            cost_f += p_cost
            prev_i, cost_i = 0,0
            ind = 0

         if c_cost < p_cost:
            cost_f += c_cost
            ind = 1
            prev_i, cost_i = prev, p_cost

      else:
         prev_i, cost_i = 0,0
         ind = 0
   return cost_f

s = "pptpp"
cost = [2,3,4,5,2]
print(solve(s, cost))