Giả sử chúng ta có một danh sách các số được gọi là cầu thang và một giá trị khác k. Chúng tôi hiện đang ở cầu thang 0 và muốn leo đến chỉ mục cuối cùng của cầu thang. Cầu thang giá trị [i] cho biết chi phí cần đạt được tại chỉ mục và trong mỗi vòng, chúng ta có thể nhảy 1, 2, ... k, cầu thang cùng một lúc. Chúng ta phải tìm số tiền tối thiểu để leo lên cầu thang cuối cùng.
Vì vậy, nếu đầu vào giống như cầu thang =[4, 11, 11, 3, 2] k =3, thì đầu ra sẽ là 9, khi chúng ta sử dụng cầu thang [4, 3, 2]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau
-
q:=một hàng đợi kết thúc kép và chèn một cặp (cầu thang [0], 0) vào đó
-
đối với tôi trong phạm vi từ 1 đến kích thước của cầu thang, hãy làm
-
while i - q [0, 1]> k, do
-
xóa mục bên trái của q
-
-
lề đường:=q [0, 0] + cầu thang [i]
-
trong khi q không trống và và curcost <=giá trị đầu tiên của mục cuối cùng của q, thực hiện
-
xóa phần tử cuối cùng khỏi q
-
-
insert (curcost, i) vào cuối q
-
-
trả về giá trị đầu tiên của mục cuối cùng của q
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
Ví dụ
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))
Đầu vào
[4, 11, 11, 3, 2], 3
Đầu ra
9