Участник:Novitskiy97/Minimum Cost to Merge Stones

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/minimum-cost-to-merge-stones/

Python 3

 
import numpy as np
 
class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        MAXN = 32
        inf = int(1e9)
 
        dp = np.array([[int(0)] * MAXN for i in range(MAXN)])
        s = np.array([int(0)] * MAXN)
 
        n = len(stones)
        if ((n-1) % (K-1) != 0):
            return -1
 
        for i in range(1, n + 1):
            s[i] = s[i-1] + stones[i-1]
        for l in range(1, n+1):
            for i in range(0, n-l+1):
                j = i + l - 1
                if (l < K):
                    dp[i][j] = 0
                elif (l == K):
                    dp[i][j] = s[j+1] - s[i]
                else:
                    dp[i][j] = inf
                    for k in range(i, j, K - 1):
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
                    if ((l-1) % (K-1) == 0):
                        dp[i][j] += s[j+1] - s[i]
 
        return dp[0][n-1]