ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে এবং আরেকটি মান k আছে। এখানে সংখ্যার আইটেমগুলি [i] সূচক i এ অবতরণের খরচগুলিকে প্রতিনিধিত্ব করে৷ যদি আমরা সূচক 0 থেকে শুরু করি এবং সংখ্যার শেষ সূচকে শেষ করি। প্রতিটি ধাপে আমরা কিছু অবস্থান X থেকে k ধাপ দূরে যে কোনো অবস্থানে লাফ দিতে পারি। শেষ সূচকে পৌঁছানোর জন্য আমাদের খরচের যোগফল কমিয়ে আনতে হবে, তাহলে ন্যূনতম যোগফল কত হবে?
সুতরাং, ইনপুট যদি nums =[2, 3, 4, 5, 6] k =2 এর মত হয়, তাহলে আউটপুট হবে 12, যেহেতু আমরা 12 এর সর্বনিম্ন খরচ পেতে 2 + 4 + 6 নির্বাচন করতে পারি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- উত্তর :=0
- h :=একটি খালি গাদা
- আমি 0 থেকে সংখ্যার আকারের মধ্যে,
- করুন
- val :=0
- যখন h খালি নয়, কর
- [val, index] :=h[0]
- যদি সূচক>=i - k, তারপর
- লুপ থেকে বেরিয়ে আসুন
- অন্যথায়,
- হিপ থেকে শীর্ষ মুছে দিন h
- উত্তর :=সংখ্যা[i] + ভ্যাল
- ঢোকান জোড়া (আন, i) স্তূপে h
- উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
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
আউটপুট
12
