পাইথনে সর্বোচ্চ k স্টেপে ফাইনাল ইনডেক্সে পৌঁছানোর ন্যূনতম খরচ বের করার প্রোগ্রাম

ধরি আমাদের একটি নাম্বার লিস্ট nums এবং আরেকটি মান k আছে। এখানে nums[i] i-তম ইনডেক্সে ল্যান্ড করার খরচ। আমরা ইনডেক্স ০ থেকে শুরু করে nums-এর লাস্ট ইনডেক্সে শেষ করব। প্রতিটি স্টেপে আমরা পজিশন X থেকে সর্বোচ্চ k স্টেপ দূরতوى যেকোনো পজিশনে জাম্প করতে পারি। লাস্ট ইনডেক্সে পৌঁছানোর জন্য খরচের সমষ্টি মিনিমাইজ করতে হবে, ন্যূনতম সমষ্টি কত?

তাই, ইনপুট যদি nums = [2, 3, 4, 5, 6], k = 2 হয়, তবে আউটপুট হবে ১২, কারণ ২ + ৪ + ৬ = ১২ ন্যূনতম খরচ দিয়ে পাওয়া যায়।

সমাধানের ধাপগুলো:

ans := 0
h := একটি খালি হিপ
i = ০ থেকে len(nums) পর্যন্ত, করুন
- val := 0
- যখন h খালি নয়, করুন
  - [val, index] := h[0]
  - যদি index >= i - k, তবে
    - লুপ থেকে বের হোন
  - অন্যথায়,
    - হিপ h-র টপ ডিলিট করুন
- ans := nums[i] + val
- (ans, i) পেয়ার হিপ h-এ ইনসার্ট করুন
ans রিটার্ন করুন

বেশি বুঝতে নিচের বাস্তবায়নটি দেখুন:

উদাহরণ

from heapq import heappush, heappop

class Solution:
    def solve(self, nums, k):
        ans = 0
        h = []
        for i in range(len(nums)):
            val = 0
            while h:
                val, index = h[0]
                if index >= i - k:
                    break
                else:
                    heappop(h)
            ans = nums[i] + val
            heappush(h, (ans, i))
        return ans

ob = Solution()
nums = [2, 3, 4, 5, 6]
k = 2
print(ob.solve(nums, k))

ইনপুট

[2, 3, 4, 5, 6], 2