โปรแกรมกำหนดต้นทุนขั้นต่ำในการสร้างสตริงที่กำหนดใน python

สมมติว่าเราต้องสร้างสตริง 'str' ที่มีความยาว n ในการสร้างสตริง เราสามารถดำเนินการได้ 2 อย่าง

• สามารถเพิ่มอักขระต่อท้าย str ได้ในราคา a
• สามารถเพิ่มสตริงย่อย sub_str ที่ส่วนท้ายของ str ได้ในราคา r

เราต้องคำนวณต้นทุนขั้นต่ำในการสร้างสตริงสตริง

ดังนั้น หากอินพุตเป็น 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.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ขนาด :=ขนาดของ str
• ที่ใหญ่ที่สุด :=รายการใหม่
• ต่ำ :=0
• สำหรับ upp ในช่วง 1 ถึง size+1 ให้ทำ
  • ในขณะที่ str[จากดัชนีต่ำถึงดัชนี upp] ไม่มีอยู่ใน str[จากดัชนี 0 ถึงดัชนีต่ำ] ให้ทำ
    • ต่ำ :=ต่ำ + 1
  • แทรก (ขึ้น - ต่ำ) ที่ส่วนท้ายที่ใหญ่ที่สุด
• c :=รายการใหม่ที่มี
• สำหรับผมในช่วง 1 ถึงขนาด ทำ
  • ถ้าที่ใหญ่ที่สุด[i] เท่ากับ 0 แล้ว
    • แทรก (องค์ประกอบสุดท้ายของ c + a) ที่ส่วนท้ายของ c
  • มิฉะนั้น
    • แทรกขั้นต่ำของ (องค์ประกอบสุดท้ายของ c + a), (c[i - ใหญ่ที่สุด[i]] + r) ที่ส่วนท้ายของ c
• คืนค่าองค์ประกอบสุดท้ายของ 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