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

假设，我们必须构建一个长度为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))

输入

5, 4, tpoint输出结果29