Solution:

It might be 'tempting' to think that the problem can be solved using a greedy approach, i.e. merge the K consecutive stones with the minimum cost in each step. But the greedy approach is not optimal, for e.g. if the stones array is [6,4,4,6] and K=2, then the greedy approach would result in a minimum cost of 42 whereas the optimal cost is 40. The greedy approach would first merge [4,4] to produce [8] then in the next step would merge [8,6] to produce [14] while the optimal approach would first merge [6,4] to produce [10] and in the next step would merge [4,6] to again produce another [10]. Thus the greedy approach incurs a cost of 22 in the first two steps but the optimal approach incurs a cost of 20.

A brute force approach would evaluate all possible 'merges' in each step. For an array of size N and merge size of K, the number of possible consecutive merges in the 1st step would be N-(K-1). In the next step, each merged state will have N-2*(K-1) possible merges and so on. Thus the total number of all possible steps is:

F(N, K-1) + F(N, K-1)*F(N, 2*(K-1)) + F(N, K-1)*F(N, 2*(K-1))*F(N, 3*(K-1)) + ... + F(N, K-1)*...*F(N, s*(K-1))

where F(N, K) = N-K and 's' is the number of steps to reach completion. We can estimate the number of steps 's' to completion by using the fact that the length of the array after all merges should be 1 if at all the stones could be merged, i.e. F(N, s*(K-1)) = 1

N-s*(K-1) = 1 or s = (N-1)/(K-1)

This relation is also useful for determining whether we can merge the stones at all or not. For e.g. if N-1 is not divisible by K-1 then we cannot merge the stones using a merge size of K, thus we return -1 in those cases.

In the worst case K=2, thus the above summation reduces to:

(N-1) + (N-1)*(N-2) + (N-1)*(N-2)*(N-3) + .... + (N-1)!

Thus the time complexity for the brute force approach is O(N!).

Thus all the above observations:

- Brute force approach has exponential space-time complexity
- Greedy approach is non-optimal

Leads us to the path of Dynamic Programming (DP).

But how do we formulate the problem recursively that will allow us to solve it using DP ? Observe that if the stones array is represented by the vector:

[s_{0}, s_{1}, ..., s_{N-1}]

and the minimum cost to merge the stones is denoted by C(0, N-1) where 0 is the starting index and N-1 is the last index then we can write the following relationship:

C(0, N-1) = min_{k} {C(0, k)+C(k+1, N-1)} where 0 <= k < N-1

This implies that the minimum cost to merge the stones of length N is equivalent to finding a split point 'k' between 0 and N-1, such that if we merge the stones from 0 to k and k+1 to N-1 separately and then merge their results such that the total cost of separately merging the stones [0, k] and [k+1, N-1] and then merging the results is minimum across all possible values of 'k'.

Let C[i][j] denote a 3-tuple (x, y, z), where 'x' represents the summation of the stones from index i to index j. 'y' represents the minimum cost to merge the stones from index i to index j and 'z' is the number of stones remaining un-merged after merging the stones from index i to j. Then we can write the following relations:

C[i][j] = (sum(stones[i:j+1]), 0, j-i+1) if j - i + 1 < K

because we cannot merge these stones as K is greater than the distance between i and j. Thus merge cost is 0. sum(stones[i:j+1]) denotes the summation of stones from i to j (in Pythonic notation).

C[i][j] = (sum(stones[i:j+1]), sum(stones[i:j+1]), 1) if j - i + 1 == K

because if distance between i and j is exactly K, then we merge these stones to a single stone with the merge cost equals to the summation of the stones from i to j. Now if j -i +1 > K, then for all k, such that i <= k < j :

x_{k} = C[i][k][0] + C[k+1][j][0]

z_{k} = C[i][k][2] + C[k+1][j][2]

y_{k} = C[i][k][1] + C[k+1][j][1] if z_{k} < K

y_{k} = C[i][k][1] + C[k+1][j][1] + x_{k} if z_{k} == K

C[i][j] = (x_{k'}, y_{k'}, z_{k'}) such that k' = argmin_{k}{y_{k}}

The final answer is C[0][N-1][1] which is the minimum cost to merge the stones from 0 to N-1.

The python code for the above is as follows:

import numpy as np, collections class Solution(object): def mergeStones(self, stones, K): n = len(stones) if (n-1) % (K-1) != 0: return -1 cached = collections.defaultdict(dict) for length in range(1, n+1): for i in range(n-length+1): j = i + length - 1 if length < K: cached[i][j] = (np.sum(stones[i:j+1]), 0, length) elif length == K: sums = np.sum(stones[i:j+1]) cached[i][j] = (sums, sums, 1) else: min_cost = float("Inf") min_cost_len, min_cost_sum = -1, 0 for k in range(i, j): a, b = cached[i][k], cached[k+1][j] if a[2] + b[2] < K: cost = a[1] + b[1] if cost < min_cost: min_cost = cost min_cost_sum = a[0] + b[0] min_cost_len = a[2] + b[2] elif a[2] + b[2] == K: cost = a[1] + b[1] + a[0] + b[0] if cost < min_cost: min_cost = cost min_cost_sum = a[0] + b[0] min_cost_len = 1 cached[i][j] = (min_cost_sum, min_cost, min_cost_len) return cached[0][n-1][1]

The run-time complexity of the above approach and code is O(N^{3}).

Categories: PROBLEM SOLVING

Tags: Dynamic Programming, Greedy Algorithm, Leetcode, Merge Stones, Recursion

### Leave a Reply

You must be logged in to post a comment.