পাইথনে স্টোন মার্জ করার ন্যূনতম খরচ খুঁজে বের করার প্রোগ্রাম

আমাদের Nটি স্টোন পাইল একটি রোয়ে সাজানো আছে। i-তম পাইলে stones[i] সংখ্যক স্টোন আছে। একটি মুভ হলো Kটি কনsekutিভ পাইলকে একটা পাইলে মার্জ করা, এই মুভের খরচ হবে এই Kটি পাইলের মোট স্টোন সংখ্যা। আমাদের সব পাইলকে একটা পাইলে মার্জ করার ন্যূনতম খরচ বের করতে হবে। যদি কোনো সমাধান না থাকে, তবে -1 রিটার্ন করুন।

উদাহরণস্বরূপ, ইনপুট nums = [3,2,4,1], K = 2 হলে আউটপুট হবে 20, কারণ:

প্রাথমিক: [3, 2, 4, 1]
[3, 2] মার্জ করলে খরচ ৫, থাকে [5, 4, 1]
[4, 1] মার্জ করলে খরচ ৫, থাকে [5, 5]
[5, 5] মার্জ করলে খরচ ১০, থাকে [10]
মোট খরচ ২০, এবং এটি ন্যূনতম।

সমাধানের ধাপসমূহ (DP)

n := nums-এর আকার
যদি (n-1) % (K-1) != 0 হয়, তবে -1 রিটার্ন করুন
dp := n x n অ্যারে ০ দিয়ে ফিল করে
sums := (n+1) আকারের অ্যারে ০ দিয়ে ফিল করে
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] += sums[j+1] - sums[i]
dp[0][n-1] রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

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