โปรแกรมหาค่าขั้นต่ำในการปีนบันไดใน Python?

สมมติว่าเรามีรายการตัวเลขที่เรียกว่าบันได และอีกค่าหนึ่งคือ k ขณะนี้เราอยู่ที่บันได 0 และต้องการปีนไปยังดัชนีสุดท้ายของบันได ค่า stair[i] หมายถึง ต้นทุนที่จะไปถึงที่ index และในแต่ละรอบ เราสามารถกระโดด 1, 2, ... k, บันไดในคราวเดียว เราต้องหาต้นทุนขั้นต่ำเพื่อปีนขึ้นบันไดสุดท้าย

ดังนั้นหากอินพุตเป็นเหมือนบันได =[4, 11, 11, 3, 2] k =3 ผลลัพธ์จะเป็น 9 ตามที่เราใช้บันได[4, 3, 2]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้

• q :=คิวแบบ double-end และใส่คู่ (stairs[0], 0) เข้าไป

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

  • ในขณะที่ i - q[0, 1]> k ทำ

    • ลบรายการจากด้านซ้ายของ q

  • curcost :=q[0, 0] + บันได[i]

  • ในขณะที่ q ไม่ว่างเปล่าและ curcost <=ค่าแรกของรายการสุดท้ายของ q ให้ทำ

    • ลบองค์ประกอบสุดท้ายออกจาก q

  • แทรก (curcost, i) ที่ส่วนท้ายของ q

• ส่งคืนค่าแรกของรายการสุดท้ายของ q

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

ตัวอย่าง

from collections import deque

class Solution:
   def solve(self, stairs, k):
      q = deque([(stairs[0], 0)])
      for i in range(1, len(stairs)):
         while i - q[0][1] > k:
            q.popleft()
         curcost = q[0][0] + stairs[i]
         while q and curcost <= q[-1][0]:
            q.pop()
         q.append((curcost, i))
      return q[-1][0]

ob = Solution()
stairs = [4, 11, 11, 3, 2]
k = 3
print(ob.solve(stairs, k))

อินพุต

[4, 11, 11, 3, 2], 3

ผลลัพธ์

9