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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

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)]
		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])


from functools import lru_cache
import itertools

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(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:
		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:
		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)]
		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):
						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] + 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:
		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:
				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)
		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):
			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:
		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:
		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):
		if (len(stones) - 1) % (k - 1):
			return -1
		cost = [[None] * len(stones) for _ in stones]

		def subCost(left, right):
			if left == right:
				return 0
			if cost[left][right] != None:
				return cost[left][right]
			if right - left + 1 == k:
				cost[left][right] = sum(stones[left:right + 1])
				return cost[left][right]
			divs = [left + i for i in range(k + 1)]
			divs[-1] = right + 1

			def moveDividers():

				def moveDivider(i):
					if i == 0:
						return False
					if divs[i] == right - (k - 1 - i):
						return moveDivider(i - 1)
					divs[i] += 1
					while (divs[i] - divs[i - 1] - 1) % (k - 1):
						divs[i] += 1
					for j in range(i + 1, len(divs) - 1):
						divs[j] = divs[j - 1] + 1
					return True
				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)
		return result


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 (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