LeetCode [1000]

1000. Minimum Cost to Merge Stones

Hard

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.

 

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,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.

Example 3:

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

@flarbear

Each step merges K piles into 1, which takes away K piles and puts back 1 in their place. This reduces the stones by K-1. If Ni is the number of stones after i merges, then we have:

N0 = N = length of stones array
N1 = N - K + 1 = N - (K-1)
N2 = N - K + 1 - K + 1 = N - (K-1)*2
Ni = N - (K - 1)*i
We eventually need some Ni to equal 1 (to represent the 1 remaining pile on success), so we have:
N - (K-1) * i == 1
N - 1 == (K-1) * i
So, N-1 is a multiple of K-1, or:
(N-1) % (K-1) == 0.

@lee215

dp[i][j][m] means the cost needed to merge stone[i] ~ stones[j] into m piles.

Initial status dp[i][i][1] = 0 and dp[i][i][m] = infinity

dp[i][j][1] = dp[i][j][k] + stonesNumber[i][j]
dp[i][j][m] = min(dp[i][mid][1] + dp[mid + 1][j][m - 1])

The origine python2 solution is a bit too long on the memorization part.
So I rewrote it in python3 with cache helper,
so it will be clear for logic.

Complexity
Time O(N^3/K), Space O(KN^2)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

public class Solution { Integer[][][] memo; int[] preSum; public int mergeStones(int[] stones, int K) { if (stones == null || stones.length == 0) return -1; int n = stones.length; if (n == 1) return 0; preSum = new int[n + 1]; for (int i = 0; i < n; i++) { preSum[i + 1] = preSum[i] + stones[i]; } if (n == K) { return preSum[n]; } if ((n - 1) % (K - 1) != 0) return -1; memo = new Integer[n][n][K + 1]; for (int i = 0; i < n; i++) { memo[i][i][1] = 0; } return calculate(stones, 0, n - 1, 1, K); } private int calculate(int[] stones, int i, int j, int piles, int K) { if ((j - i + 1 - piles) % (K - 1) != 0) { return Integer.MAX_VALUE; } if (memo[i][j][piles] != null) { return memo[i][j][piles]; } int cost = Integer.MAX_VALUE; if (piles == 1) { int prev = calculate(stones, i, j, K, K); if (prev != Integer.MAX_VALUE) { cost = prev + preSum[j + 1] - preSum[i]; } } else { for (int mid = i; mid < j; mid++) { int left = calculate(stones, i, mid, 1, K); if (left >= cost) continue; int right = calculate(stones, mid + 1, j, piles - 1, K); if (right >= cost) continue; cost = Math.min(cost, left + right); } } memo[i][j][piles] = cost; return cost; } }