Giả sử chúng ta có N đống đá xếp thành một hàng. Ở đây đống thứ i có đá [i] số đá. Một nước đi bao gồm gộp K cọc liên tiếp thành một cọc, bây giờ chi phí của lần di chuyển này bằng tổng số đá trong K số cọc này. Chúng ta phải tìm ra mức chi phí tối thiểu để gộp tất cả các đống đá thành một đống. Nếu không có giải pháp nào như vậy, hãy trả về -1.
Vì vậy, nếu đầu vào giống như nums =[3,2,4,1], K =2, thì đầu ra sẽ là 20, bởi vì, ban đầu có [3, 2, 4, 1]. Sau đó hợp nhất [3, 2] với giá 5, và chúng ta có [5, 4, 1]. Sau đó hợp nhất [4, 1] với giá 5, và chúng ta có [5, 5]. Sau đó hợp nhất [5, 5] với giá 10, và chúng ta có [10]. Vì vậy, tổng chi phí là 20 và đây là chi phí tối thiểu.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của nums
-
nếu (n-1) mod (K-1) không phải là 0, thì
-
trả về -1
-
-
dp:=một n x n mảng và điền bằng 0
-
tổng:=n mảng có kích thước (n + 1) và điền bằng 0
-
đối với tôi trong phạm vi từ 1 đến n, hãy thực hiện
-
sums [i]:=sums [i-1] + nums [i-1]
-
-
đối với độ dài trong phạm vi từ K đến n, thực hiện
-
đối với tôi trong phạm vi từ 0 đến n-length, hãy thực hiện
-
j:=i + length-1
-
dp [i, j]:=infinity
-
đối với t trong phạm vi i đến j-1, cập nhật từng bước theo K-1, thực hiện
-
dp [i] [j] =tối thiểu là dp [i, j] và (dp [i, t] + dp [t + 1, j])
-
-
nếu (j-i) mod (K-1) giống 0, thì
-
dp [i, j]:=dp [i, j] + tổng [j + 1] -sums [i]
-
-
-
-
trả về dp [0, n-1]
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn
import heapq
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