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

Cho chuỗi str độ dài n. Có hai phép toán xây dựng:

• Thêm một ký tự vào cuối chuỗi với chi phí a
• Thêm một chuỗi con sub_str vào cuối chuỗi với chi phí r

Tìm chi phí tối thiểu để xây dựng chuỗi str.

Ví dụ: a = 5, r = 4, str = 'tpoint' → kết quả 29.

Chi tiết: xây dựng lần lượt 't', 'tp', 'tpo', 'tpoi', 'tpoin' (mỗi bước +1 ký tự, chi phí 5), cuối cùng thêm chuỗi con 't' (chi phí 4). Tổng = 5×5 + 4 = 29.

Thuật toán giải quyết (Dynamic Programming + Z-function)

1. Tính mảng largest[i] = độ dài lớn nhất của chuỗi con bắt đầu tại i xuất hiện trước đó trong chuỗi (dùng Z-algorithm)
2. DP: c[0] = a, với i = 1..n-1:
   • Nếu largest[i] == 0: c[i] = c[i-1] + a (chỉ có thể thêm ký tự)
   • Ngược lại: c[i] = min(c[i-1] + a, c[i - largest[i]] + r) (chọn min giữa thêm ký tự vs thêm chuỗi con)
3. Trả về c[n-1]

Ví dụ minh họa

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