数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究Python程序：确定构建给定字符串的最小成本
假设我们必须构建一个长度为n的字符串'str'。为了构建该字符串，我们可以执行两个操作。
- 可以以成本a将字符添加到str的末尾。
- 可以以成本r将子字符串sub_str添加到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。
为了解决这个问题，我们将遵循以下步骤：
- size := str的长度
- largest := 一个新的列表
- low := 0
- for upp in range 1 to size+1:
- while str[从索引low到索引upp] 不存在于 str[从索引0到索引low] 中:
- low := low + 1
- 在largest的末尾插入(upp - low)
- while str[从索引low到索引upp] 不存在于 str[从索引0到索引low] 中:
- c := 一个包含a的新列表
- for i in range 1 to size:
- if largest[i] == 0:
- 在c的末尾插入(c的最后一个元素 + a)
- 否则：
- 在c的末尾插入 min((c的最后一个元素 + a), (c[i - largest[i]] + r))
- if largest[i] == 0:
- 返回c的最后一个元素
示例
让我们看下面的实现以更好地理解：
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
更新于：2021年10月11日
971 次浏览
广告