โปรแกรมหาต้นทุนการลบน้อยที่สุดเพื่อไม่ให้ตัวอักษรซ้ำติดกันใน Python

ปัญหา

สตริง s และ cost[i] ต้นทุนลบตัวอักษร i หาต้นทุนน้อยที่สุดลบตัวอักษรบางตัว ให้ไม่มีตัวอักษรซ้ำติดกัน (ลบพร้อมกัน ต้นทุนไม่เปลี่ยน)

ตัวอย่าง

s="pptpp", cost=[2,3,4,5,2] → 4 (ลบ p ตัวแรกและสุดท้าย ต้นทุน 2+2=4 เหลือ "ptp")

ขั้นตอนการแก้ปัญหา

1. cost_f := 0, ind := 0, prev_i := 0, cost_i := 0
2. วน i 1..len(s)-1:
   • cur, c_cost := s[i], cost[i], prev, p_cost := s[i-1], cost[i-1]
   • ถ้า ind == 1: prev, p_cost := prev_i, cost_i
   • ถ้า cur == prev:
     • ถ้า c_cost >= p_cost: cost_f += p_cost; prev_i, cost_i = 0,0; ind = 0
     • ถ้า c_cost < p_cost: cost_f += c_cost; ind = 1; prev_i, cost_i = prev, p_cost
   • มิฉะนั้น: prev_i, cost_i = 0,0; ind = 0
3. คืน cost_f

การนำไปใช้งาน (Python)

def solve(s, cost):
    cost_f = 0
    ind = 0
    prev_i = 0
    cost_i = 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