পাইথনে সিঁড়ির শীর্ষে উঠতে ন্যূনতম খরচ পেতে প্রোগ্রাম খুঁজে পেতে?

ধরুন আমাদের কাছে সিঁড়ি নামক সংখ্যার একটি তালিকা এবং আরেকটি মান k আছে। আমরা বর্তমানে 0 সিঁড়িতে আছি এবং সিঁড়ির শেষ সূচকে উঠতে চাই। মান সিঁড়ি [i] নির্দেশ করে যে সূচকে পৌঁছানোর খরচ এবং প্রতিটি রাউন্ডে আমরা একবারে 1, 2, ... k, সিঁড়ি লাফ দিতে পারি। শেষ সিঁড়িতে ওঠার জন্য আমাদের সর্বনিম্ন খরচ খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি সিঁড়ির মত হয় =[4, 11, 11, 3, 2] k =3, তাহলে আউটপুট হবে 9, যেমন আমরা সিঁড়ি ব্যবহার করি[4, 3, 2]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব

q :=একটি ডবল শেষ সারি এবং এটিতে একটি জোড়া (সিঁড়ি[0], 0) ঢোকান
আমি রেঞ্জ 1 থেকে সিঁড়ির আকারের জন্য, করুন
- যখন i - q[0, 1]> k, do
  - q
    এর বাম থেকে আইটেম সরান
- curcost :=q[0, 0] + সিঁড়ি[i]
- যখন q খালি নয় এবং curcost <=q এর শেষ আইটেমের প্রথম মান, do
  - q
    থেকে শেষ উপাদান মুছুন
- q
  এর শেষে সন্নিবেশ করুন (curcost, i)
q
এর শেষ আইটেমের প্রথম মান ফেরত দিন

আরও ভালোভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি

উদাহরণ

সংগ্রহ থেকে dequeclass সমাধান আমদানি করুন:def solve(self, stairs, k):q =deque([(সিঁড়ি[0], 0)]) এর জন্য i রেঞ্জে(1, len(সিঁড়ি)):যখন আমি - q[0][1]> k:q.popleft() curcost =q[0][0] + সিঁড়ি[i] যখন q এবং curcost <=q[-1][0]:q.pop() q যোগ করুন /প্রে> ইনপুট
 [4, 11, 11, 3, 2], 3
 আউটপুট
 9