确定在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
热门推荐
1 训练狗狗憋尿
2 狗狗追踪训练
3 狗狗训练要多少钱
5 深圳狗狗训练
6 训练狗狗唤回
7 狗狗叫怎么训练
8 狗狗训练班
10 狗狗社会化训练
11 狗狗叫回训练
12 广州狗狗训练学校
13 狗狗训练躺下
14 狗狗随行训练
15 训练狗狗巡回
16 狗狗要怎么训练
17 狗狗喂食训练
18 训练狗狗躺下