No one wished me luck just kidding (am i though ). On a more serious note, the DP approach was really interesting! I definitely needed some inspiration for this approach(LC Discuss FTW ). The key insight for me was the constraint that the length of an array should satisfy:

`(n-1)%(k-1)==0`

Illustration at the end to showcase this point.

Although it seems straight forward, it helps us memoize information later pretty well!(once we’ve broken down our problem into smaller sub-problems).

Then we split our larger array into smaller pieces, which satisfy this constraint, and in our DP matrix store the `min_cost`

for a subarray from i to j. `dp[i][j] = min_cost to combine subarray from i to j`

.

Here is my final solution:

```
class Solution:
def mergeStones(self, stones: List[int], K: int) -> int:
"""
Using dp
dp[i][j] = state, min_cost to combine stones from index i to j(inclusive)
dp[i][j] = min(dp[i][temp]+dp[temp+1][j] for temp in range(i,j, K-1))
so temp = i, i+(K-1), i+2*(K-1)...., because we know adding (K-1) to a pile(of min size 1) will result in a combinable length of stones.
"""
if K>2 and len(stones)%(K-1)!=1: # every combine, reduces len by K-1, leaving 1 element at the end, special case for K=2, which can always combine
return -1
cum_sum = [0]*(len(stones)+1) # array to store cumulative sum. Will help us to find sum of array from i to j index. Need to start with 0 to take care of base cases later.
my_dict = {}
for i in range(len(stones)):
cum_sum[i+1] = cum_sum[i]+stones[i]
return self.dp_helper(0, len(stones)-1, K, stones, cum_sum, my_dict)
def dp_helper(self, start, end, K, stones, cum_sum,my_dict):
if end-start+1<K:
return 0
if (start,end) in my_dict: # if we've already calculated the min_cost for this range.
return my_dict[(start,end)]
# Sorry, about the extended parameter list, you can just nest the helper function. I prefer having it separate (for some reason :shrug:).
# Essentially res = min(self.dp(start,temp)+self.dp(temp+1,end) for temp in range(i,j,K-1))
# Minimum of all combinations of left + right.
res = min(self.dp_helper(start, temp, K, stones, cum_sum, my_dict) + self.dp_helper(temp+1, end, K, stones, cum_sum, my_dict) for temp in range(start, end, K-1))
# Splitting start-end range into various [prefix(start-temp)][suffix(temp+1,end)], and calculating min sum for each smaller range, and storing it in map later.
if (K>2 and (end-start+1)%(K-1)==1) or K-1==1: # basically (end-start)%(K-1)==0
res+= cum_sum[end+1]-cum_sum[start]
my_dict[(start, end)] = res
return res
```

Some illustrations to drive the point home:

Hope that helps. Thanks for the question!!