There are 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.
Find the minimum cost to merge all piles of stones into one pile.  If it is impossible, return -1.
 

Example 1:
Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation: 
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.


Example 2:
Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.


Example 3:
Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation: 
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.

 
Note:

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

Difficulty: interview

Starter code:

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        

Solutions:
class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        if (n - 1) % (K - 1) != 0:
            return -1
        prefix = [0]
        for s in stones:
            prefix.append(prefix[-1] + s)
        @lru_cache(None)
        def dp(i, j):
            if j - i + 1 < K:
                return 0
            res = 0
            if (j - i) % (K - 1) == 0:
                res = prefix[j+1] - prefix[i]
            return res + min(dp(i, mid) + dp(mid+1, j) for mid in range(i, j, K - 1))
        return dp(0, n - 1)

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        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]+stones[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]

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        
        @lru_cache(None)
        def recursive(i, j, piles):
            if j - i + 1 < K: return 0
            if piles == 1:
                return recursive(i, j, K) + pre_sum[j+1] - pre_sum[i]
            else:
                min_cost = float('inf')
                for k in range(i, j, K - 1):
                    min_cost = min(min_cost, recursive(i, k, 1) + recursive(k + 1, j, piles - 1))
                return min_cost
            
        n = len(stones)
        if (n - 1) % (K - 1) != 0:
            return -1
        pre_sum = [0] * (n + 1)
        for i in range(n):
            pre_sum[i + 1] = pre_sum[i] + stones[i]

        return recursive(0, n - 1, 1)

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        k = K
        if (n < k and n != 1) or (n - 1) % (k - 1) != 0:
            return -1
        if n == 1:
            return 0
        
        dp = [[-1 for _ in range(n)] for _ in range(n)]  # dp[i][j] stores min cost to reduce [i, j] as much as possible
        self.solve(stones, 0, n - 1, k, dp)
        # print(dp)
        return dp[0][n - 1]
    
    def solve(self, stones, l, r, k, dp):
        length = r - l + 1
        if length < k:
            dp[l][r] = 0
            return
        if length == k:
            dp[l][r] = sum(stones[l:r+1])
            return
        res = float('inf')
        for m in range(l, r):
            length = length
            length_l = m - l + 1
            length_r = r - m
            
            rem = k - 1 if length % (k - 1) == 0 else length % (k - 1)
            rem_l = k - 1 if length_l % (k - 1) == 0 else length_l % (k - 1)
            rem_r = k - 1 if length_r % (k - 1) == 0 else length_r % (k - 1)
            rem_total = k - 1 if (rem_l + rem_r) % (k - 1) == 0 else (rem_l + rem_r) % (k - 1)
            if rem_total == rem and (rem_l + rem_r) <= k:
                if dp[l][m] == -1:
                    self.solve(stones, l, m, k, dp)
                if dp[m + 1][r] == -1:
                    self.solve(stones, m + 1, r, k, dp)
                # print('lets check {} to {} and {}'.format(l, m, r))
                # print(dp[l][m], dp[m+1][r])
                res = min(res, dp[l][m] + dp[m+1][r])
                
        dp[l][r] = res
        if rem == 1:
            dp[l][r] += sum(stones[l:r+1])
        
    
# class Solution:
#     def mergeStones(self, stones: List[int], K: int) -> int:
#         n = len(stones)
#         k = K
#         if (n < k and n != 1) or (n - k) % (k - 1) != 0:
#             return -1
#         if n == 1:
#             return 0
        
#         return self.comp_min(stones, k, -1)
    
#     def comp_min(self, stones, k, locked):  # can't do a merge which only involves the first 'locked' stones
#         n = len(stones)
#         if n == k:
#             return sum(stones)
        
#         total_cur_cost = float('inf')
        
#         for i in range(max(0, locked - k + 2), n - k + 1):
#             cur_cost = sum(stones[i:i+k])
#             new_stones = stones[:i] + [cur_cost] + stones[i+k:]
            
#             new_locked = i - 1
            
#             tmp = self.comp_min(new_stones, k, new_locked)
            
#             total_cur_cost = min(total_cur_cost, cur_cost + tmp)
                
#         return total_cur_cost


from functools import lru_cache
import itertools

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        # dp[i][j] means the minimum cost needed to merge stones[i] ~ stones[j].
        # Time  complexity: O(N^3 / K)
        # Space complexity: O(KN^2)
        n = len(stones)
        if (n - 1) % (K - 1): return -1
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]

        @lru_cache(None)
        def dp(i, j):
            if j - i + 1 < K: return 0

            res = min(dp(i, mid) + dp(mid + 1, j) for mid in range(i, j, K - 1))

            if (j - i) % (K - 1) == 0:
                res += prefix[j + 1] - prefix[i]

            return res

        return dp(0, n - 1)


from functools import lru_cache
import itertools

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        # Time  complexity: O(N^3 / K)
        # Space complexity: O(KN^2)
        n = len(stones)
        if (n - 1) % (K - 1): return -1
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]

        @lru_cache(None)
        def dp(i, j):
            if j - i + 1 < K: return 0

            res = min(dp(i, mid) + dp(mid + 1, j) for mid in range(i, j, K - 1))

            if (j - i) % (K - 1) == 0:
                res += prefix[j + 1] - prefix[i]

            return res

        return dp(0, n - 1)


class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        dp, N, Sum, H = {}, len(stones), {-1: 0}, {}
        for i in range(N):
            j, dp[i], H[i], Sum[i] = i, {}, {}, Sum[i - 1] + stones[i]       
            while j > -1:
                H[i][j] = (i-j+1)%(K-1)+(K-1)*(1//(1+(i-j+1)%(K-1)))
                if i - j < K - 1: dp[i][j] = 0    
                else:
                    dp[i][j] =  dp[i][i] + dp[i - 1][j]
                    for k in range(j + 1, i + 1):
                        if H[i][k] + H[k - 1][j] == H[i][j] or H[i][k] + H[k - 1][j] == K:
                            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k - 1][j])     
                    if H[i][j] == 1: dp[i][j] += Sum[i] - Sum[j - 1]
                j = j - 1           
        return dp[N-1][0]*(1//H[N-1][0]) - min(H[N-1][0]-1, 1) 

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        k = K
        if (n < k and n != 1) or (n - 1) % (k - 1) != 0:
            return -1
        if n == 1:
            return 0
        
        dp = [[-1 for _ in range(n)] for _ in range(n)]  # dp[i][j] stores min cost to reduce [i, j] as much as possible
        self.solve(stones, 0, n - 1, k, dp)
        return dp[0][n - 1]
    
    def solve(self, stones, l, r, k, dp):
        length = r - l + 1
        if length < k:
            dp[l][r] = 0
            return
        if length == k:
            dp[l][r] = sum(stones[l:r+1])
            return
        res = float('inf')
        for m in range(l, r):
            length = length
            length_l = m - l + 1
            length_r = r - m
            
            rem = k - 1 if length % (k - 1) == 0 else length % (k - 1)
            rem_l = k - 1 if length_l % (k - 1) == 0 else length_l % (k - 1)
            rem_r = k - 1 if length_r % (k - 1) == 0 else length_r % (k - 1)
            rem_total = k - 1 if (rem_l + rem_r) % (k - 1) == 0 else (rem_l + rem_r) % (k - 1)
            if rem_total == rem and (rem_l + rem_r) <= k:
                if dp[l][m] == -1:
                    self.solve(stones, l, m, k, dp)
                if dp[m + 1][r] == -1:
                    self.solve(stones, m + 1, r, k, dp)
                res = min(res, dp[l][m] + dp[m+1][r])
                
        dp[l][r] = res
        if rem == 1:
            dp[l][r] += sum(stones[l:r+1])


class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        total = len(stones)
        if (total-1) % (K-1):
            return -1
        
        
        prefix = [0] * (total+1)
        for i in range(total):
            prefix[i+1] = prefix[i]+stones[i]
        
        import functools
        @functools.lru_cache(None)
        def dfs(i, j):
            if j-i+1 < K:
                return 0
            res = min(dfs(i,k)+dfs(k+1,j) for k in range(i, j, K-1))
            if (j-i) % (K-1) == 0:
                res += prefix[j+1]-prefix[i]
                
            return res
        
        return dfs(0, total-1)

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        '''
        dp[i][j][k]: the min cost to merge stone[i: j + 1] into k piles
        the range for consecutive piles of stone[i:j + 1] to be k piles after merging can be divided into two parts (for stones[:n] be finally merged into 1 pile):
            1. a sub-range from the start to the devide that is sured to be merged in to 1 pile: dp[i][divide][1]
                divide goes from start by K - 1 step to make this happen: dp[i][divide][1] < math.inf
            2. a sub-range from the divide + 1 to the end (not guaranteed to be realistic): dp[divide + 1][k - 1]
        The longer ranges are always merged from the smaller ones, no matter how the smaller ones were merged from. That is why this is a DP problem.
        '''
        n = len(stones)
        if K > 2 and n % (K - 1) != 1:
            return -1
        
        dp = [[[math.inf] * (K + 1) for i in range(n)] for j in range(n)]
        for i in range(n):
            dp[i][i][1] = 0
            
        presum = [stones[0]]
        for i in range(1, n):
            presum.append(presum[i - 1] + stones[i])
            
        def stones_in_range(i, j):
            return presum[j] - presum[i - 1] if i > 0 else presum[j]
        
        for rangelen in range(2, n + 1):
            for start in range(n + 1 - rangelen):
                end = start + rangelen - 1
                for k in range(2, K + 1):
                    for divide in range(start, end, K - 1):
                        dp[start][end][k] = min(dp[start][end][k], dp[start][divide][1] + dp[divide + 1][end][k - 1])
                if dp[start][end][K] < math.inf:
                    dp[start][end][1] = dp[start][end][K] + stones_in_range(start, end)
                    
        return dp[0][n - 1][1]

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        if (len(stones) - 1) % (K - 1) != 0:
            return -1
        
        prefix = [0]
        for stone in stones:
            prefix.append(prefix[-1] + stone)
            
        memo = {}

        def recur(i: int, j: int, m: int):
            key = str(i) + ',' + str(j) + ',' + str(m)
            if key in memo:
                return memo[key]
            
            if (j - i + 1 - m) % (K - 1):
                return 91111111
            
            if (j - i + 1) < K:
                memo[key] = 0
                return 0

            if m == 1:
                if j - i + 1 == K:
                    memo[key] = prefix[j + 1] - prefix[i]
                    return memo[key]
                else:
                    return recur(i, j, K) + prefix[j + 1] - prefix[i]

            min_sum = 91111111
            for mid in range(i, j, K - 1):
                cur_sum = recur(i, mid, 1) + recur(mid + 1, j, m - 1)
                min_sum = min(min_sum, cur_sum)

            memo[key] = min_sum
            return min_sum
        
        return recur(0, len(stones) - 1, 1)

from typing import List
import numpy
import sys
import bisect


class Solution:
  def mergeStones(self, stones: List[int], K: int) -> int:

    tmp = 0
    n = len(stones)
    dims = (n, n)
    dp = numpy.zeros(dims)
    presum = numpy.zeros(n+1)

    if (n - 1) % (K - 1) != 0:
      return -1

    for index, stone in enumerate(stones):
      tmp += stone
      presum[index+1] = tmp

    for rlen in range(K, n + 1):
      for i in range(0, n - rlen + 1):
        end = i + rlen - 1
        dp[i][end] = sys.maxsize
        for j in range(i, end, K - 1):
          dp[i][end] = min(dp[i][end], dp[i][j] + dp[j + 1][end])

        if (rlen - 1) % (K - 1) == 0:
          dp[i][end] += presum[end+1] - presum[i]

    return int(dp[0][n - 1])

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        dp = [[[math.inf for k in range(K + 1)] for j in range(n)] for i in range(n)]
        # dp[i][j][k]: min cost of merging from i to j (inclusive) and finally having k piles
        for i in range(n):
            dp[i][i][1] = 0
            
        pre_sum = [0] * n
        pre_sum[0] = stones[0]
        for i in range(1, n):
            pre_sum[i] = pre_sum[i - 1] + stones[i]
        
        def range_sum(i, j):
            if i == 0:
                return pre_sum[j]
            else:
                return pre_sum[j] - pre_sum[i - 1]
            
        for merge_len in range(2, n + 1): # 枚举区间长度
            for start in range(n - merge_len + 1): # 枚举区间左端点
                end = start + merge_len - 1 # 区间右端点
                for k in range(2, K + 1): 
                    for middle in range(start, end, K - 1): # 枚举分割点，左区间start~middle，右区间middle+1~end
                        dp[start][end][k] = min(dp[start][end][k], dp[start][middle][1] + dp[middle + 1][end][k - 1])
                if dp[start][end][K] < math.inf: # 可以make a move，merge start ~ end 成 1 个pile
                    dp[start][end][1] = dp[start][end][K] + range_sum(start, end)
        return dp[0][n-1][1] if dp[0][n-1][1] < math.inf else -1

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        # dp[i][j][k]: min cost of merging from i to j and finally having k piles
        n = len(stones)
        dp = [[[math.inf for k in range(K + 1)] for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i][1] = 0
            
        pre_sum = [0] * n
        pre_sum[0] = stones[0]
        for i in range(1, n):
            pre_sum[i] = pre_sum[i - 1] + stones[i]
        
        def range_sum(i, j):
            if i == 0:
                return pre_sum[j]
            else:
                return pre_sum[j] - pre_sum[i - 1]
        
        for length in range(2, n+1):
            for i in range(n - length + 1):
                j = i + length - 1
                # 最少两个，最多K个pile
                for k in range(2, K + 1):
                    for middle in range(i, j, K-1):
                        # 分成 1 和 k-1堆，合并起来是 k
                        dp[i][j][k] = min(dp[i][j][k], dp[i][middle][1] + dp[middle + 1][j][k - 1])
                if dp[i][j][K] < math.inf:
                    # 合并成 1个pile
                    dp[i][j][1] = dp[i][j][K] + range_sum(i, j)
        return dp[0][n-1][1] if dp[0][n - 1][1] < math.inf else -1


class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)

        dp = [[[math.inf for k in range(K + 1)] for j in range(n)] for i in range(n)]
        # dp[i][j][k]: min cost of merging from i to j and finally having k piles
        for i in range(n):
            dp[i][i][1] = 0 
        
        pre_sum = [0] * (n + 1)
        for i in range(1, n + 1):
            pre_sum[i] = pre_sum[i - 1] + stones[i - 1]
            
        for merge_len in range(2, n + 1):
            for start in range(n - merge_len + 1):
                end = start + merge_len - 1 
                for k in range(2, K + 1):
                    for middle in range(start, end, K-1):
                        dp[start][end][k] = min(dp[start][end][k], dp[start][middle][1] + dp[middle + 1][end][k - 1])
                    if dp[start][end][K] < math.inf:
                        dp[start][end][1] = dp[start][end][K] + pre_sum[end + 1] - pre_sum[start]
        return dp[0][n-1][1] if dp[0][n-1][1] < math.inf else -1

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        inf = float('inf')
        if (n - 1) % (K - 1) is not 0:
            return -1
        
        prefix = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] + stones[i - 1]
            
        @lru_cache(None)
        def dp(i, j, k):
            if i == j:
                # cost to make one pile from one pile is 0, otherwise impossible
                return 0 if k == 1 else inf
            if k == 1:
                return dp(i, j, K) + prefix[j + 1] - prefix[i]
            return min(dp(i, m, 1) + dp(m + 1, j, k - 1) for m in range(i, j))
            
        return dp(0, n - 1, 1)

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        N = len(stones)
        presum = [0 for _ in range(N + 1)]
        dp = [[[math.inf for _ in range(K + 1)] for _ in range(N)] for _ in range(N)]
        
        if (N - 1) % (K - 1) != 0:
            return -1
        
        for i in range(N):
            presum[i + 1] = presum[i] + stones[i]
            
        for i in range(N):
            dp[i][i][1] = 0
        
        for length in range(2, N + 1):
            for start in range(N - length + 1):
                end = start + length - 1
                for mid in range(start, end):
                    for k in range(2, K + 1):
                        if k > length: 
                            continue
                        if dp[start][mid][1] == math.inf or dp[mid + 1][end][k - 1] == math.inf:
                            continue
                            
                        dp[start][end][k] = min(dp[start][end][k], dp[start][mid][1] + dp[mid + 1][end][k - 1])
                    
                    if dp[start][end][K] != math.inf:
                        dp[start][end][1] = dp[start][end][K] + presum[end + 1] - presum[start]
                    
        if dp[0][N - 1][1] == math.inf:
            return -1
        return dp[0][N - 1][1]

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        if (len(stones) - 1) % (K - 1) != 0:
            return -1
        
        presum = 0
        presum_list = [presum]
        for cost in stones:
            presum += cost
            presum_list.append(presum)
        
        # dp[i][j][k]: cost that merges into k piles: from ith pile to jth pile
        n = len(stones)
        dp = [[[math.inf] * (K + 1) for _ in range(n)] for _ in range(n)]
        
        for i in range(n):
            dp[i][i][1] = 0
        
        for pile_length in range(1, n + 1):
            # pile_length = j - i + 1
            for i in range(n - pile_length + 1):
                j = pile_length + i - 1
                for possible_k in range(2, min(pile_length, K) + 1):
                    for t in range(i, j):
                        dp[i][j][possible_k] = min(dp[i][j][possible_k], dp[i][t][possible_k - 1] + dp[t + 1][j][1])
                dp[i][j][1] = min(dp[i][j][1], dp[i][j][K] + presum_list[j + 1] - presum_list[i])
        
        return dp[0][n - 1][1]

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        # Time Complexity: O(N^3 K)
        
        self.dp = {}
        self.prefix = [0] + list(itertools.accumulate(stones))
        
        ret = self.merge(stones, 0, len(stones) - 1, 1, K)
        
        return ret
        
    def merge(self, stones, start: int, end: int, num_parts: int, K: int):
        if (start, end, num_parts) in self.dp:
            return self.dp[(start, end, num_parts)]
        
        if end - start + 1 < num_parts:
            return -1
        
        if end - start + 1 == num_parts:
            return 0
        
        window_sum = self.prefix[end + 1] - self.prefix[start] 
        
        if num_parts == 1:
            split = self.merge(stones, start, end, K, K)
            
            if split == -1:
                ret = -1
            else:
                ret = window_sum + split
        else:
            candidates = []
            
            for i in range(start, end):
                left = self.merge(stones, start, i, 1, K)
                right = self.merge(stones, i + 1, end, num_parts - 1, K)
                
                
                if left >= 0 and right >= 0:
                    candidates.append(left + right)
            
            if candidates:
                ret = min(candidates)
            else:
                ret = -1
                
        self.dp[(start, end, num_parts)] = ret
        return ret



# 1000. Minimum Cost to Merge Stones
class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        N = len(stones)
        if (N - 1) % (K - 1): 
            return -1
        dp = [[0] * N for _ in range(N)]
        
        for l in range(K, N+1):
            for i in range(N-l+1):
                dp[i][i+l-1] = float('inf')
                for x in range(i, i+l-1, K-1):
                    dp[i][i+l-1] = min(dp[i][i+l-1], dp[i][x] + dp[x+1][i+l-1])
                dp[i][i+l-1] += (sum(stones[i:i+l]) if (l-1)%(K-1) == 0 else 0)
        
        return dp[0][N-1]

class Solution:
    def mergeStones(self, stones, k):
    
        # quick check to see if this number of piles can be merged. 
        if (len(stones)-1)%(k-1): 
            return -1

        cost = [[None]*len(stones) for _ in stones]

        def subCost(left, right):

            # Base case: there is no cost to \"merging\" one pile
            if left == right: 
                return 0

            if cost[left][right] != None: 
                return cost[left][right]

            # Base case: a single merge is just the sum of the elements.  
            if (right - left + 1) == k: 
                cost[left][right] = sum(stones[left:right+1])
                return cost[left][right]

            # find k-1 division points.  Each division except the last is the start index of a sub-array
            # ie. if stones = [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ], left = 0 right = 8 divs = [0, 3, 8, 9]
            # then sub-arrays are as follows: [0, 1, 2] [3, 4, 5, 6, 7]  [8] 
            # the above divs would incidentally be valid for k = 3. 

            divs = [ left + i for i in range(k+1)]
            divs[-1] = right + 1  # set the last divider to one past the subarray. 
            # for example above, divs is initialized to -> [0, 1, 2, 9].  The first and last divider never change

            def moveDividers():
                # loop through dividers to move, starting at last one.  
                # if the last one is at the end, move the next one up. 

                def moveDivider(i): 
                    if i == 0: 
                        return False

                    # if the div we're looking at is smashing all dividers to its right against the right end of the array. 
                    # If k = 3, i = 1, we have 1 divider to our right.  Leave 1 space for each divider to our right.
                    # division 0 stays at 0 
                    # div 1 can go to 2.  = right - (k - 1 - i)
                    if divs[i] == ( right - (k - 1 - i)):
                        # switch to the next divider to the left
                        return moveDivider(i-1)

                    # move this divider to the next usable spot given where the left neighbor div is. 
                    divs[i] += 1
                    while (divs[i] - divs[i-1] - 1)%(k-1):
                        divs[i] += 1

                    # stack all following divs next to each other and this one. []
                    for j in range(i+1, len(divs)-1):
                        divs[j] = divs[j-1] + 1

                    return True

                # start by moving the rightmost divider
                return moveDivider(len(divs) - 2)

            best = float('inf')
            while 1:
                subSum = 0
                for div_i in range(len(divs)-1):
                    subSum += subCost(divs[div_i], divs[div_i+1] - 1) 
                best = min(best, subSum) 
                if not moveDividers():
                    break

            result = best + sum(stones[left:right+1])
            cost[left][right] = result
            return result

        result = subCost(0, len(stones)-1)
        #print(cost)
        return result 

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        # Time Complexity: O(N^3 K)
        # Space Complexity: O(N^2 K)
        
        self.dp = {}
        self.prefix = [0] + list(itertools.accumulate(stones))
        
        ret = self.merge(stones, 0, len(stones) - 1, 1, K)
        
        return ret
        
    def merge(self, stones, start: int, end: int, num_parts: int, K: int):
        if (start, end, num_parts) in self.dp:
            return self.dp[(start, end, num_parts)]
        
        if end - start + 1 < num_parts:
            return -1
        
        if end - start + 1 == num_parts:
            return 0
        
        window_sum = self.prefix[end + 1] - self.prefix[start] 
        
        if num_parts == 1:
            split = self.merge(stones, start, end, K, K)
            
            if split == -1:
                ret = -1
            else:
                ret = window_sum + split
        else:
            candidates = []
            
            for i in range(start, end):
                left = self.merge(stones, start, i, 1, K)
                right = self.merge(stones, i + 1, end, num_parts - 1, K)
                
                
                if left >= 0 and right >= 0:
                    candidates.append(left + right)
            
            if candidates:
                ret = min(candidates)
            else:
                ret = -1
                
        self.dp[(start, end, num_parts)] = ret
        return ret



class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        self.dp = {}
        
        
        ret = self.merge(stones, 0, len(stones) - 1, 1, K)
        
        return ret
        
    def merge(self, stones, start: int, end: int, num_parts: int, K: int):
        if (start, end, num_parts) in self.dp:
            return self.dp[(start, end, num_parts)]
        
        if end - start + 1 < num_parts:
            return -1
        
        if end - start + 1 == num_parts:
            return 0
        
        window_sum = sum(stones[start:end + 1])
        
        if num_parts == 1:
            split = self.merge(stones, start, end, K, K)
            
            if split == -1:
                ret = -1
            else:
                ret = window_sum + split
        else:
            candidates = []
            
            for i in range(start, end):
                left = self.merge(stones, start, i, 1, K)
                right = self.merge(stones, i + 1, end, num_parts - 1, K)
                
                
                if left >= 0 and right >= 0:
                    candidates.append(left + right)
            
            if candidates:
                ret = min(candidates)
            else:
                ret = -1
                
        self.dp[(start, end, num_parts)] = ret
        return ret



class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones) 
        
        inf = float('inf')
        prefix = [0] * (n + 1)
        
        for i in range(n): 
            prefix[i + 1] = prefix[i] + stones[i]
            
        import functools
        
        @functools.lru_cache(None) 
        def dp(i, j, m): 
            if i == j: 
                return 0 if m == 1 else inf
            if m == 1: 
                return dp(i, j, K) + prefix[j + 1] - prefix[i]
            
            return min(dp(i, mid, 1) + dp(mid + 1, j, m - 1) for mid in range(i, j))
        
        res = dp(0, n - 1, 1)
        
        return res if res < inf else -1 

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        if K > 2 and n % (K - 1) != 1:
            return -1
        
        dp = [[[math.inf] * (K + 1) for i in range(n)] for j in range(n)]
        for i in range(n):
            dp[i][i][1] = 0
            
        presum = [stones[0]]
        for i in range(1, n):
            presum.append(presum[i - 1] + stones[i])
            
        def stones_in_range(i, j):
            return presum[j] - presum[i - 1] if i > 0 else presum[j]
        
        for rangelen in range(2, n + 1):
            for start in range(n + 1 - rangelen):
                end = start + rangelen - 1
                for k in range(2, K + 1):
                    for divide in range(start, end, K - 1):
                        dp[start][end][k] = min(dp[start][end][k], dp[start][divide][1] + dp[divide + 1][end][k - 1])
                        print(start, end, k, divide, dp[start][end][k])
                if dp[start][end][K] < math.inf:
                    dp[start][end][1] = dp[start][end][K] + stones_in_range(start, end)
                    
        return dp[0][n - 1][1]

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        if (n - 1) % (K - 1):
            return -1
        
        s = [0]
        for num in stones:
            s.append(s[-1] + num)
        
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = float('inf')
                for m in range(i, j, K - 1):
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j] + (0 if (j - i) % (K - 1) else s[j + 1] - s[i]))
        
        return -1 if dp[0][-1] == float('inf') else dp[0][-1]
        
        
        @functools.lru_cache(None)
        def f(i, j):
            if i == j:
                return 0
            ans = float('inf')
            m = i
            while m < j:
                ans = min(ans, f(i, m) + f(m + 1, j) + (0 if (j - i) % (K - 1) else s[j + 1] - s[i]))
                m += K - 1
                
            return ans
        
        ans = f(0, n - 1)
        return -1 if ans == float('inf') else ans

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        if (n-1)%(K-1) != 0:
            return -1
        dp = [[0]*n for i in range(n)]
        sums = [0]*(n+1)
        for i in range(1, n+1):
            sums[i] = sums[i-1] + stones[i-1]
        for l in range(K, n+1):
            for i in range(n-l+1):
                j = i+l-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]


class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        if (n - 1) % (K - 1):
            return -1
        prefix = [0]*(n+1)
        for i in range(1, n+1):
            prefix[i] = prefix[i-1] + stones[i-1]
        import functools
        @functools.lru_cache(None)
        def dp(i, j):
            if j - i + 1 < K:
                return 0
            res = min(dp(i, mid) + dp(mid+1, j) for mid in range(i, j, K-1))
            if (j - i) % (K - 1) == 0:
                res += prefix[j + 1] - prefix[i]
            return res
        return dp(0, n-1)
    
#         n = len(stones)
#         if (n - 1) % (K - 1): return -1
#         prefix = [0] * (n + 1)
#         for i in range(n):
#             prefix[i + 1] = prefix[i] + stones[i]

#         import functools
#         @functools.lru_cache(None)
#         def dp(i, j):
#             if j - i + 1 < K: return 0
#             res = min(dp(i, mid) + dp(mid + 1, j) for mid in range(i, j, K - 1))
#             if (j - i) % (K - 1) == 0:
#                 res += prefix[j + 1] - prefix[i]
#             return res
#         return dp(0, n - 1)