2
\$\begingroup\$

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))
\$\endgroup\$
3
  • \$\begingroup\$ What sort of the issues it rans into? \$\endgroup\$
    – vnp
    Sep 8 '19 at 21:37
  • \$\begingroup\$ 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? \$\endgroup\$
    – EML
    Sep 8 '19 at 22:14
  • 3
    \$\begingroup\$ Several DP solutions are posted in the discussion board on LeetCode. \$\endgroup\$
    – GZ0
    Sep 8 '19 at 23:02
1
\$\begingroup\$

Without even doing anything clever regarding the algorithm, this:

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

can be cleaned up as

    merged_count = sum(stones[start:start + k])
    new_count = merged_count + count
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.