How hard is LeetCode 1000. Minimum Cost to Merge Stones?

LeetCode 1000. Minimum Cost to Merge Stones is rated Hard on LeetCode.

What topics does LeetCode 1000. Minimum Cost to Merge Stones cover?

LeetCode 1000. Minimum Cost to Merge Stones is tagged Array, Dynamic Programming and Prefix Sum on LeetCode.

Minimum Cost to Merge Stones — LeetCode 1000 Python Solution

HardArrayDynamic ProgrammingPrefix Sum

Problem: #1000
Pattern: Prefix Sum
Reading time: 3 min
Source: leetcode.com

The problem

There are n piles of stones arranged in a row. The ith pile has stones[i] stones.

Example

Input: stones = [3,2,4,1], k = 2
Output: 20
Explanation: We start with [3, 2, 4, 1].

Python solution

Python

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        if (n - 1) % (K - 1):
            return -1
        s = list(accumulate(stones, initial=0))
        f = [[[inf] * (K + 1) for _ in range(n + 1)] for _ in range(n + 1)]
        for i in range(1, n + 1):
            f[i][i][1] = 0
        for l in range(2, n + 1):
            for i in range(1, n - l + 2):
                j = i + l - 1
                for k in range(1, K + 1):
                    for h in range(i, j):
                        f[i][j][k] = min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1])
                f[i][j][1] = f[i][j][K] + s[j] - s[i - 1]
        return f[1][n][1]

Complexity

Measure	Complexity
Time	O(n·m) (typical)
Space	O(n·m) or optimized auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1000. Minimum Cost to Merge Stones is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1000. Minimum Cost to Merge Stones?: LeetCode 1000. Minimum Cost to Merge Stones is rated Hard on LeetCode.
What topics does LeetCode 1000. Minimum Cost to Merge Stones cover?: LeetCode 1000. Minimum Cost to Merge Stones is tagged Array, Dynamic Programming and Prefix Sum on LeetCode.