Problem statement

https://binarysearch.com/problems/Crush-Consecutive-Numbers/

Solution

Equal to Leetcode 1000 Minimum Cost to Merge Stones.

Complexity

Time is O(n^3/k), space is O(n^2).

Code

class Solution:
    def solve(self, stones, K):
        acc = [0] + list(accumulate(stones))
        if (len(stones) - 1) % (K - 1) != 0: return -1
        
        @lru_cache(None)
        def dfs(i, j, k):
            if i + 1 == j: return 0

            cand = float("inf")
            for l in range(i+1, j, K - 1):
                k2 = K if k == 2 else k - 1
                l2 = j if k == 2 else l
                cand = min(cand, dfs(i, l, K) + dfs(l, j, k2) + acc[l2] - acc[i])
                
            return cand
        
        result = dfs(0, len(stones), K)
        return result if result != float("inf") else -1