โปรแกรมค้นหาต้นทุนขั้นต่ำในการผสานหินใน Python

สมมุติว่าเรามีกองหิน N กองเรียงกันเป็นแถว ที่นี่กองที่ i มีหินจำนวน [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 :=ขนาดของ nums

• ถ้า (n-1) mod (K-1) ไม่ใช่ 0 แล้ว

  • กลับ -1

• dp :=หนึ่ง n x n อาร์เรย์ และเติม 0

• sums :=n อาร์เรย์ของขนาด (n+1) และเติมด้วย 0

• สำหรับผมอยู่ในช่วง 1 ถึง n ทำ

  • sums[i] :=sums[i-1]+nums[i-1]

• สำหรับความยาวในช่วง K ถึง n ทำ

  • สำหรับฉันในช่วง 0 ถึง n-length ทำ

    • j :=i+length-1

    • dp[i, j] :=อินฟินิตี้

    • สำหรับ 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] + ผลรวม[j+1]-ผลรวม[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

ผลลัพธ์

20