To solve this problem, we need to determine the minimum cost to merge all piles of stones into one pile, where each merge operation combines K consecutive piles into one, with the cost being the sum of the stones in those K piles. If it's impossible to merge all piles into one, we return -1.
Approach
- Feasibility Check: For merging N piles into one using K-way merges, the number of piles reduced per merge is (K-1). Thus, (N-1) must be divisible by (K-1) to make merging possible. If not, return -1.
- Prefix Sum: Compute the prefix sum array to quickly calculate the sum of any subarray of stones.
- Dynamic Programming (DP): Use a DP array
dp[i][j]wheredp[i][j]is the minimum cost to merge the subarray from indexitojinto the minimum possible number of piles (or one if feasible).- Base Case:
dp[i][i] = 0(single pile has no merge cost). - Recurrence Relation: For each segment length
l, compute the minimum cost by splitting the segment into subsegments and merging them. If the segment length allows merging into one pile, add the sum of the segment to the cost.
- Base Case:
Solution Code
def min_cost_merge_stones(stones, k):
n = len(stones)
if n == 1:
return 0
if (n - 1) % (k - 1) != 0:
return -1
# Compute prefix sum (1-based)
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i-1] + stones[i-1]
# Initialize DP table
dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dp[i][i] = 0
# Fill DP table for all segment lengths
for length in range(2, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
# Split into subsegments step by k-1
for m in range(i, j, k-1):
dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j])
# If we can merge into one pile, add the sum
if (length - 1) % (k - 1) == 0:
dp[i][j] += prefix[j] - prefix[i-1]
return dp[1][n]
# Example usage
stones = [1, 2, 3, 4, 5]
k = 3
print(min_cost_merge_stones(stones, k)) # Output: 21
Explanation
- Feasibility Check: The check
(n-1) % (k-1) == 0ensures that we can reduce the number of piles from N to 1 using K-way merges. - Prefix Sum: This allows us to get the sum of any subarray in O(1) time, which is crucial for calculating merge costs.
- DP Table: For each segment length, we consider all possible splits into subsegments. The step size of
k-1in the split ensures that the subsegments can be merged into the required number of piles to form a valid K-way merge. Adding the sum of the segment when feasible completes the merge cost calculation.
This approach efficiently computes the minimum merge cost using dynamic programming, ensuring optimal substructure and overlapping subproblems are handled correctly. The time complexity is O(n³/(k-1)), which is feasible for typical problem constraints.


作者声明:本文包含人工智能生成内容。