Chương trình xác định chi phí tối thiểu để xây dựng một chuỗi nhất định trong python

Giả sử, chúng ta phải xây dựng một chuỗi 'str' có độ dài n. Để xây dựng chuỗi, chúng ta có thể thực hiện hai thao tác.

• Một ký tự có thể được thêm vào cuối str với giá a.
• Một chuỗi con sub_str có thể được thêm vào cuối chuỗi với chi phí r.

Chúng tôi phải tính toán chi phí tối thiểu để xây dựng chuỗi str.

Vì vậy, nếu đầu vào là a =5, r =4, str ='tpoint', thì đầu ra sẽ là 29.

Để tạo chuỗi 'tpoint', chi phí được mô tả bên dưới -

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.

Tổng chi phí là 5 + 5 + 5 + 5 + 5 + 4 =29.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• size:=kích thước của str
• lớn nhất:=một danh sách mới
• thấp:=0
• đối với upp trong phạm vi từ 1 đến kích thước + 1, hãy thực hiện
  • trong khi str [từ chỉ mục thấp đến chỉ mục upp] không có trong str [từ chỉ mục 0 đến chỉ mục thấp], hãy thực hiện
    • thấp:=low + 1
  • chèn (upp - thấp) vào cuối lớn nhất
• c:=một danh sách mới chứa
• đối với tôi trong phạm vi từ 1 đến kích thước, hãy thực hiện
  • nếu [i] lớn nhất bằng 0, thì
    • chèn (phần tử cuối cùng của c + a) vào cuối c
  • nếu không,
    • chèn tối thiểu (phần tử cuối cùng của c + a), (c [i - lớn nhất [i]] + r) vào cuối c
• trả về phần tử cuối cùng của c

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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'))

Đầu vào

5, 4, 'tpoint'

Đầu ra

29