Chương trình tìm chi phí tối thiểu gộp đá trong Python

Mô tả bài toán

Cho N đống đá, đống i có stones[i] viên. Mỗi lần gộp K đống liên tiếp thành một, chi phí = tổng số đá. Tìm chi phí tối thiểu gộp thành 1 đống, hoặc -1 nếu không thể.

Ví dụ

nums = [3,2,4,1], K = 2 -> 20 (gộp [3,2]->5, [4,1]->5, [5,5]->10).

Giải thuật (DP khoảng)

1. Nếu (n-1) % (K-1) != 0 -> trả về -1.
2. dp[i][j]: chi phí tối thiểu gộp đoạn i..j thành số đống hợp lệ.
3. sums: prefix sum để tính tổng nhanh.
4. Duyệt độ dài từ K đến n, cắt đoạn tại các bước K-1.
5. Nếu đoạn có thể gộp thành 1 đống ((j-i) % (K-1) == 0), cộng thêm tổng đoạn.

Triển khai Python

def solve(nums, K):
    n = len(nums)
    if (n - 1) % (K - 1) != 0:
        return -1
    dp = [[0] * n for _ in range(n)]
    sums = [0] * (n + 1)
    for i in range(1, n + 1):
        sums[i] = sums[i - 1] + nums[i - 1]
    for length in range(K, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for t in range(i, j, K - 1):
                dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j])
            if (j - i) % (K - 1) == 0:
                dp[i][j] += sums[j + 1] - sums[i]
    return dp[0][n - 1]

nums = [3, 2, 4, 1]
K = 2
print(solve(nums, K))

Đầu vào

[3,2,4,1], 2

Đầu ra

20