1000. Minimum Cost to Merge Stones

Comments

Problem Setting

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.

Variable Type Description
stones list an array of stones with the merging cost
K int the maximum number of consecutive piles

Interactive Python Execution

Pythontutor is an awesome website which allows us to execute the code and visualize the flow of the code and variables taking account into data structure and stored values.

In [1]:
from IPython.display import IFrame
IFrame("https://pythontutor.com/iframe-embed.html#code=class%20Solution%28object%29%3A%0A%20%20%20%20def%20mergeStones%28self,%20A,%20K%29%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20len%28A%29%0A%20%20%20%20%20%20%20%20if%20%28N%20-%201%29%20%25%20%28K%20-%201%29%3A%20return%20-1%0A%20%20%20%20%20%20%20%20INF%20%3D%20float%28'inf'%29%0A%20%20%20%20%20%20%20%20memo%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20prefix%20%3D%20%5B0%5D%20%23%20prefix%20sum%0A%20%20%20%20%20%20%20%20for%20x%20in%20A%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20prefix.append%28prefix%5B-1%5D%20%2B%20x%29%0A%20%20%20%20%20%20%20%20def%20dp%28i,%20j,%20m%29%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20%28j%20-%20i%20%2B%201%20-%20m%29%20%25%20%28K%20-%201%29%3A%20return%20INF%20%20%23%20optimize%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20%28i,%20j,%20m%29%20in%20memo%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20memo%5Bi,%20j,%20m%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20i%20%3D%3D%20j%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%200%20if%20m%20%3D%3D%201%20else%20INF%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20m%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20dp%28i,%20j,%20K%29%20%2B%20prefix%5Bj%20%2B%201%5D%20-%20prefix%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20INF%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20mid%20in%20range%28i,%20j,%20K%20-%201%29%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20min%28res,%20dp%28i,%20mid,%201%29%20%2B%20dp%28mid%20%2B%201,%20j,%20m%20-%201%29%29%0A%20%20%20%20%20%20%20%20%20%20%20%20memo%5Bi,%20j,%20m%5D%20%3D%20res%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20res%0A%20%20%20%20%20%20%20%20res%20%3D%20dp%280,%20N%20-%201,%201%29%0A%20%20%20%20%20%20%20%20return%20res%20if%20res%20%3C%20INF%20else%200%0A%20%20%20%20%20%20%20%20%0Astones%20%3D%20%5B3,5,1,2,6%5D%0AK%20%3D%203%0As%20%3D%20Solution%28%29%0As.mergeStones%28stones,%20K%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false", width=1000, height=500)
Out[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,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

Solution from Lee215

In [2]:
# Solution from Lee215
class Solution(object):
    def mergeStones(self, A, K):
        N = len(A)
        if (N - 1) % (K - 1): return -1
        INF = float('inf')
        memo = {}
        prefix = [0] # prefix sum
        for x in A:
            prefix.append(prefix[-1] + x)

        def dp(i, j, m):
            if (j - i + 1 - m) % (K - 1): return INF  # optimize
            if (i, j, m) in memo:
                return memo[i, j, m]
            if i == j:
                res = 0 if m == 1 else INF
            else:
                if m == 1:
                    res = dp(i, j, K) + prefix[j + 1] - prefix[i]
                else:
                    res = INF
                    for mid in range(i, j, K - 1):
                        res = min(res, dp(i, mid, 1) + dp(mid + 1, j, m - 1))
            memo[i, j, m] = res
            return res
        res = dp(0, N - 1, 1)
        return res if res < INF else 0
In [3]:
# Example 1
stones = [3,2,4,1] 
K = 2
s = Solution()
s.mergeStones(stones, K)
Out[3]:
20
In [4]:
# Example 2
stones = [3,2,4,1]
K = 3
s = Solution()
s.mergeStones(stones, K)
Out[4]:
-1
In [5]:
# Example 3
stones = [3,5,1,2,6]
K = 3
s = Solution()
s.mergeStones(stones, K)
Out[5]:
25

Step-by-step understanding

  1. Initilization
Variable Description
N the length of a given array stones
INF a float infinity
memo intermediate dictionary-based tables with input argument i, j, m
prefix a look-up list storing the cumulative sum for the given array

Example of variables

In [6]:
stones = [3,5,1,2,6]
K = 3
In [7]:
N = len(stones)
INF = float('inf')
memo = {}
prefix = [0] # prefix sum
for x in stones:
    prefix.append(prefix[-1] + x)
In [8]:
N
Out[8]:
5
In [9]:
prefix
Out[9]:
[0, 3, 8, 9, 11, 17]

Comments

Comments powered by Disqus