Chương trình tìm chi phí tối thiểu cắt gậy trong Python

Cho gậy dài n, mảng cuts vị trí cắt. Chi phí một lần cắt = độ dài đoạn gậy đang cắt. Thứ tự cắt tùy ý. Tìm tổng chi phí tối thiểu.

Ví dụ: n = 7, cuts = [5,1,4,3], đầu ra = 16 (thứ tự [3,5,1,4]: cắt 3 từ 7→7, cắt 5 từ 4→4, cắt 4 từ 2→2, cắt 1 từ 3→3, tổng=16).

Giải pháp

Interval DP (DP trên đoạn) - bài toán cắt gậy kinh điển:

• cuts := [0] + sorted(cuts) + [n]
• m := len(cuts)
• cost := ma trận m x m điền 0
• Với k từ 2 đến m-1 (độ dài đoạn):
  • Với i từ 0 đến m-1:
    • j := i + k
    • Nếu j >= m: continue
    • cost[i][j] = (cuts[j]-cuts[i]) + min(cost[i][s] + cost[s][j] for s in range(i+1, j))
• Trả về cost[0][m-1]

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(n, cuts):
    cuts = [0] + sorted(cuts) + [n]
    m = len(cuts)
    cost = [[0]*m for _ in range(m)]
    for k in range(2, m):
        for i in range(m):
            j = i + k
            if j >= m:
                continue
            cost[i][j] = (cuts[j]-cuts[i]) + min(cost[i][s] + cost[s][j] for s in range(i+1, j))
    return cost[0][m-1]

n = 7
cuts = [5,1,4,3]
print(solve(n, cuts))

Đầu vào

7, [5,1,4,3]

Đầu ra

16