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