पायथन में स्टोन्स को मर्ज करने की न्यूनतम लागत खोजने का प्रोग्राम

मान लीजिए हमारे पास N स्टोन्स के ढेर एक पंक्ति में व्यवस्थित हैं। यहां i-वें ढेर में stones[i] संख्या में स्टोन्स हैं। एक चाल में K लगातार ढेर को एक ढेर में मर्ज करना शामिल है, अब इस चाल की लागत इन K ढेर में स्टोन्स की कुल संख्या के बराबर है। हमें सभी स्टोन्स के ढेर को एक ढेर में मर्ज करने की न्यूनतम लागत ढूंढनी है। यदि ऐसा कोई समाधान नहीं है तो, -1 वापस करें।

उदाहरण के लिए, यदि इनपुट nums = [3,2,4,1], K = 2 है, तो आउटपुट 20 होगा, क्योंकि, प्रारंभ में [3, 2, 4, 1] है। फिर [3, 2] को लागत 5 से मर्ज करें, और हमारे पास [5, 4, 1] है। उसके बाद [4, 1] को लागत 5 से मर्ज करें, और हमारे पास [5, 5] है। फिर [5, 5] को लागत 10 से मर्ज करें, और हमारे पास [10] है। तो, कुल लागत 20 थी, और यह न्यूनतम है।

हल करने के चरण

n := len(nums)
यदि (n-1) % (K-1) != 0, तो -1 वापस करें।
dp := एक n x n ऐरे और 0 से भरें
sums := आकार (n+1) का ऐरे और 0 से भरें
i को 1 से n तक लूप चलाएं:
- sums[i] := sums[i-1] + nums[i-1]
length को K से n तक लूप चलाएं:
- i को 0 से n-length तक लूप चलाएं:
  - j := i + length - 1
  - dp[i][j] := infinity
  - t को i से j-1 तक, प्रत्येक चरण में K-1 से अपडेट करते हुए लूप चलाएं:
    - dp[i][j] = min(dp[i][j], dp[i][t] + dp[t+1][j])
  - यदि (j-i) % (K-1) == 0, तो:
    - dp[i][j] := dp[i][j] + sums[j+1] - sums[i]
dp[0][n-1] वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

import heapq
def solve(nums, K):
    n = len(nums)
    if (n-1) % (K-1) != 0:
        return -1
    dp = [[0]*n for _ in range(n)]
    sums = [0]*(n+1)
    for i in range(1, n+1):
        sums[i] = sums[i-1] + nums[i-1]
    for length in range(K, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for t in range(i, j, K-1):
                dp[i][j] = min(dp[i][j], dp[i][t] + dp[t+1][j])
            if (j-i) % (K-1) == 0:
                dp[i][j] += sums[j+1] - sums[i]
    return dp[0][n-1]

nums = [3,2,4,1]
K = 2
print(solve(nums, K))

इनपुट

[3,2,4,1], 2