पायथन में पत्थरों को मिलाने के लिए न्यूनतम लागत खोजने का कार्यक्रम

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=अंकों का आकार
अगर (n-1) मॉड (K-1) 0 नहीं है, तो
- वापसी -1
dp :=एक n x n सरणी और 0 से भरें
sums :=n आकार की सरणी (n+1) और 0 से भरें
1 से n की सीमा में i के लिए, करें
- रकम [i] :=रकम [i-1]+nums[i-1]
K से n तक की लंबाई के लिए, करें
- मेरे लिए 0 से n-लंबाई की सीमा में, करें
  - जे:=मैं+लंबाई-1
  - डीपी [i, जे]:=अनंत
  - t श्रेणी में i से j-1 के लिए, K-1 द्वारा प्रत्येक चरण में अपडेट करें, करें
    - dp[i][j] =न्यूनतम dp[i, j] और (dp[i, t] + dp[t+1, j])
  - अगर (j-i) mod (K-1) 0 के समान है, तो
    - dp[i, j] :=dp[i, j] + sums[j+1]-sums[i]
वापसी डीपी [0, एन -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