โปรแกรมค้นหาค่าใช้จ่ายในการลบขั้นต่ำเพื่อหลีกเลี่ยงการทำซ้ำตัวอักษรใน Python

สมมติว่าเรามีสตริง s และอาร์เรย์ของจำนวนเต็มอื่นที่เรียกว่า cost โดยที่ cost[i] แทนค่าของการลบอักขระ ith ใน s เราต้องหาต้นทุนขั้นต่ำในการลบเพื่อไม่ให้มีตัวอักษรสองตัวติดกัน เราต้องจำไว้ว่าเราจะลบตัวละครที่เลือกพร้อมกัน ดังนั้นหลังจากลบตัวละครแล้ว ค่าใช้จ่ายในการลบตัวละครอื่นจะไม่เปลี่ยนแปลง

ดังนั้น หากอินพุตเป็น s ="pptpp" ราคา =[2,3,4,5,2] ผลลัพธ์จะเป็น 4 เพราะถ้าเราลบ p ตัวแรกและตัวสุดท้ายออกด้วยราคา 2+2 =4 แล้ว สตริงจะเป็น "ptp" ที่นี่ไม่มีอักขระที่เหมือนกันสองตัวปรากฏขึ้นทีละตัว

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

• cost_f :=0
• ผม :=1
• ind :=0
• สำหรับ i ในช่วง 1 ถึงขนาด s - 1 ทำ
  • cur :=s[i], c_cost :=cost[i]
  • ก่อนหน้า :=s[i-1], p_cost :=cost[i-1]
  • ถ้า ind เหมือนกับ 1 แล้ว
    • ก่อนหน้า :=prev_i, p_cost :=cost_i
  • ถ้า cur เหมือนกับก่อนหน้าแล้ว
    • ถ้า c_cost>=p_cost แล้ว
      • cost_f :=cost_f + p_cost
      • prev_i :=0, cost_i :=0
      • ind :=0
    • ถ้า c_cost
    • cost_f :=cost_f + c_cost
    • ind :=1
    • prev_i :=ก่อนหน้า cost_i :=p_cost
• มิฉะนั้น
  • prev_i :=0, cost_i :=0
  • ind :=0

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

def solve(s, cost):
   cost_f = 0
   i = 1
   ind = 0

   for i in range(1, len(s)):
      cur, c_cost = s[i], cost[i]
      prev, p_cost = s[i-1], cost[i-1]
      if ind == 1:
         prev, p_cost = prev_i, cost_i

      if cur == prev:
         if c_cost >= p_cost:
            cost_f += p_cost
            prev_i, cost_i = 0,0
            ind = 0

         if c_cost < p_cost:
            cost_f += c_cost
            ind = 1
            prev_i, cost_i = prev, p_cost

      else:
         prev_i, cost_i = 0,0
         ind = 0
   return cost_f

s = "pptpp"
cost = [2,3,4,5,2]
print(solve(s, cost))

อินพุต

"pptpp", [2,3,4,5,2]

ผลลัพธ์

4