确定在python中构建给定字符串的最低成本的程序

Z时代
2024-01-10
分类：综合

假设，我们必须构建一个长度为 n 的字符串 'str'。要构建字符串，我们可以执行两个操作。

一个字符可以添加到 str 的末尾，成本为 a。
可以将子字符串 sub_str 添加到成本 r 的 str 末尾。

我们必须计算构建字符串 str 的最低成本。

因此，如果输入类似于 a = 5, r = 4, str = 'tpoint'，那么输出将是 29。

要构建字符串 'tpoint'，成本如下所述 -

str = 't'; a new character added, therefore the cost is 5.
str = 'tp'; a new character added, therefore the cost is 5.
str = 'tpo'; a new character added, therefore the cost is 5.
str = 'tpoi'; a new character added, therefore the cost is 5.
str = 'tpoin'; a new character added, therefore the cost is 5.
str = 'tpoint'; substring 't' is added, therefore the cost is 4.

总成本为 5 + 5 + 5 + 5 + 5 + 4 = 29。

示例

让我们看看以下实现以获得更好的理解 -

def solve(a, r, str):
   size = len(str)
   largest = []
   low = 0
   for upp in range(1, size+1):
      while str[low:upp] not in str[:low]:
         low += 1
      largest.append(upp - low)
   c = [a]
   for i in range(1, size):
      if largest[i] == 0:
         c.append(c[-1] + a)
      else:
         c.append(min(c[-1] + a, c[i - largest[i]] + r))
   return c[-1]
print(solve(5, 4, 'tpoint'))