# LeetCode - Merging piles of stones

This is a LeetCode Problem

You have a pile of stones presented as an array. On each turn you must merge k consecutive piles of stones, starting from any pile you wish. You must continue merging piles until you are left with one pile only. You must do this with minimum overall cost, where the cost is the sum of the ongoing cost plus the sum of all the piles being merged

If this isn't possible, return -1. If this is possible, return the minimum overall cost

Example

If k = 2 and the stones = [3,2,4,1]

Round 1: Merge stones 3 and 2 => Cost = 5, stones = [5, 4, 1]

Round 2: Merge stones 4 and 1 => Cost = 5 + (4+1) = 10, stones = [5, 5]

Round 3: Merge the piles 5 and 5 => Cost 10 + (5+5)= 20, stones = [10]

The minimum overall cost is 20

My code is below. It runs into issues for large piles of stones such as

stones = [29, 59, 31, 7, 51, 99, 47, 40, 24, 20, 98, 41, 42, 81, 92, 55]

k = 2

How do I improve this code to quickly calculate the answer for large piles of stones?

Thank you

def helper(stones, k, count, min_count):
# Basecase - if only one pile of stones, set minimum count to lowest value of current minimum and new minimum
if len(stones) == 1:
min_count = min(count, min_count)
return min_count
# Set last index
last_index = len(stones) - k + 1
for start in range(last_index):
new_count = count + sum(stones[start:start + k])
merged_count = sum(stones[start:start + k])
new_list = stones[:start] + [merged_count] + stones[start + k:]
min_count = helper(new_list, k, new_count, min_count)
return min_count

def merge_stones(stones, k):
lng = len(stones)
# Verify if solution is possible
if lng < k or (lng - 1) % (k - 1) != 0:
return -1
# Calculate solution
minimum = helper(stones, k, 0, 99999999)
# Return solution
return minimum

if __name__ == "__main__":
stones = [3, 2, 4, 1]
k = 2
print(merge_stones(stones, k))

• What sort of the issues it rans into?
– vnp
Commented Sep 8, 2019 at 21:37
• It takes for ever to deal with long lists. I suspect it calculates the correct answer as it calculates all of LeetCode's shorter test-samples correctly. My understanding is the code speeds up with dynamic programming (memoisation) but I don't know how to implement it here? Commented Sep 8, 2019 at 22:14
• Several DP solutions are posted in the discussion board on LeetCode.
– GZ0
Commented Sep 8, 2019 at 23:02

    new_count = count + sum(stones[start:start + k])

    merged_count = sum(stones[start:start + k])