สมมติว่าเรามีรายการตัวเลข nums และอีกค่าหนึ่งคือ k ที่นี่รายการที่ nums[i] หมายถึงต้นทุนของการลงจอดที่ดัชนี i หากเราเริ่มต้นจากดัชนี 0 และสิ้นสุดที่ดัชนีสุดท้ายของ nums ในแต่ละขั้นตอน เราสามารถกระโดดจากตำแหน่ง X ไปที่ตำแหน่งใดๆ ได้ไกลถึง k ก้าว เราต้องลดผลรวมของต้นทุนเพื่อให้ได้ดัชนีสุดท้าย แล้วผลรวมขั้นต่ำจะเป็นเท่าไหร่
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 3, 4, 5, 6] k =2 ผลลัพธ์จะเป็น 12 เนื่องจากเราสามารถเลือก 2 + 4 + 6 เพื่อให้ได้ต้นทุนขั้นต่ำที่ 12
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตอบ :=0
- h :=กองที่ว่างเปล่า
- สำหรับ i ในช่วง 0 ถึงขนาดของ nums ให้ทำ
- ค่า :=0
- ในขณะที่ h ไม่ว่าง ให้ทำ
- [val, index] :=h[0]
- ถ้าดัชนี>=i - k แล้ว
- ออกมาจากวงจร
- มิฉะนั้น
- ลบด้านบนออกจากฮีป h
- ans :=nums[i] + val
- ใส่คู่ (ans, 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
