Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1000 with 18 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1000 # by problem number
lcpy gen -s minimum_cost_to_merge_stones # by problem name
n piles of stones arranged in a row. The i^th pile has stones[i] stones.
A move consists of merging exactly k consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these k piles.
Return the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.
Input: stones = [3,2,4,1], k = 2
Output: 20
Input: stones = [3,2,4,1], k = 3
Output: -1
Input: stones = [3,5,1,2,6], k = 3
Output: 25
n == stones.length1 <= n <= 301 <= stones[i] <= 1002 <= k <= 30class Solution:
# Time: O(n^3 / k * k) = O(n^3) over intervals with k-step splits
# Space: O(n^2)
def merge_stones(self, stones: list[int], k: int) -> int:
n = len(stones)
if n == 1:
return 0
if (n - 1) % (k - 1) != 0:
return -1
prefix = [0] * (n + 1)
for i, stones_count in enumerate(stones):
prefix[i + 1] = prefix[i] + stones_count
# dp[i][j] = min cost to merge stones[i..j] down to the minimum possible pile count
dp = [[0] * n for _ in range(n)]
for length in range(k, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = min(dp[i][mid] + dp[mid + 1][j] for mid in range(i, j, k - 1))
if (j - i) % (k - 1) == 0:
dp[i][j] += prefix[j + 1] - prefix[i]
return dp[0][n - 1]
| Time | Space |
|---|---|
| O(n^3 / k * k) = O(n^3) over intervals with k-step splits | O(n^2) |