資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告