1000. Minimum Cost to Merge Stones (Dynamic Programming) 19.11.27 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


Solution: ------------------------------------------------- Dynamic Programming ------- https://www.youtube.com/watch?v=FabkoUzs64o
----------------------------------------------------------- O(N^3/K) T and O(KN^2) S
class Solution(object):
    def mergeStones(self, stones, K):
        """
        :type stones: List[int]
        :type K: int
        :rtype: int
        """
        if not stones or K <= 0:
            return -1
        n = len(stones)
        if (n - 1) % (K - 1) != 0:
            return -1
        sum = [0] * (n + 1)
        for i in range(n):
            sum[i + 1] = sum[i] + stones[i]

        dp = [[[float('inf') for k in range(K + 1)] for j in range(n + 1)] for i in range(n + 1)]
        
        for i in range(n):
            dp[i][i][1] = 0

        for step in range(1,n + 1):
            for i in range(0, n - step + 1):
                j = i + step - 1
                for k in range(1,K + 1):
                    for mid in range(i,j):
                        if k != 1:
                            dp[i][j][k] = min(dp[i][j][k], dp[i][mid][1] + dp[mid + 1][j][k - 1])
                        else:
                            dp[i][j][k] = min(dp[i][j][k], dp[i][mid][1] + dp[mid + 1][j][K - 1] + (sum[j + 1] - sum[i]))

        return dp[0][n-1][1] if dp[0][n-1][1] != float('inf') else -1