โปรแกรมหาค่าใช้จ่ายน้อยที่สุดในการรวมก้อนหินใน Python

มี N กองหิน เรียงติดกัน กอง i มี stones[i] ก้อน แต่ละครั้งรวม K กองติดกันเป็น 1 กอง ค่าใช้จ่าย = ผลรวมหินใน K กองนั้น หาค่าใช้จ่ายรวมน้อยที่สุดรวมเป็น 1 กอง (ถ้าไม่ได้คืน -1)

ตัวอย่าง: nums=[3,2,4,1], K=2 ผลลัพธ์ 20

วิธีแก้ปัญหา (DP ก้อน)

1. ถ้า (n-1) % (K-1) != 0 คืน -1
2. dp[i][j] = ค่าใช้จ่ายน้อยที่สุดรวมกอง i..j
3. sums = prefix sum
4. วน length = K..n คำนวณ dp[i][j] โดยลองแบ่งทุก t ก้าว K-1
5. ถ้า (j-i) % (K-1) == 0 บวก sums[j+1]-sums[i]

ตัวอย่างโค้ด

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))

อินพุต

[3,2,4,1], 2

เอาต์พุต

20