Chương trình tìm chi phí xóa tối thiểu tránh ký tự lặp liền kề trong Python

Cho chuỗi s và mảng cost (cost[i] = chi phí xóa s[i]). Xóa đồng thời các ký tự được chọn sao cho không có 2 ký tự giống nhau liền kề. Tìm chi phí nhỏ nhất.

Ví dụ: s="pptpp", cost=[2,3,4,5,2] → 4. Xóa 'p' đầu (2) và 'p' cuối (2) → "ptp".

Giải thuật (Duyệt 1 lần, giữ lại ký tự chi phí cao)

1. Duyệt i từ 1..n-1, so sánh s[i] với s[i-1] (hoặc ký tự giữ lại trước đó nếu vừa xóa).
2. Nếu cùng ký tự:
   • Xóa ký tự chi phí nhỏ hơn: cộng chi phí nhỏ vào kết quả, giữ lại ký tự chi phí lớn (cập nhật prev_i, cost_i, ind=1).
   • Nếu chi phí bằng nhau: xóa cái trước (ind=0).
3. Nếu khác ký tự: reset ind=0.

Ví dụ minh họa

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

Đầu vào

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

Đầu ra

4