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
- Method: dp
class Solution { public int mergeStones(int[] stones, int K) { int n = stones.length; if((n - 1) % (K - 1) != 0) return -1; int[][][] dp = new int[n][n][K + 1]; int[] sum = new int[n + 1]; for(int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i]; for(int[][] dd: dp) for(int[] d: dd) Arrays.fill(d, Integer.MAX_VALUE); for(int i = 0; i < n; i++) dp[i][i][1] = 0; for(int l = 2; l <= n; l++){ for(int start = 0; start <= n - l; start++){ int end = start + l - 1; for(int k = 2; k <= K; k++){ for(int mid = start; mid < end; mid += K - 1) dp[start][end][k] = Math.min(dp[start][end][k], dp[start][mid][1] + dp[mid + 1][end][k - 1]); dp[start][end][1] = dp[start][end][K] + sum[end + 1] - sum[start]; } } } return dp[0][n - 1][1]; } }