สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums ซึ่งแต่ละค่าเป็นตัวกำหนดหน่วยของเวลาที่ใช้ในการทำงานให้เสร็จ เราสามารถข้ามงานที่ไม่ต่อเนื่องกันได้ เราต้องหาเวลาขั้นต่ำที่ใช้ในการทำงานทั้งหมดให้เสร็จ
ดังนั้น หากอินพุตเป็น nums =[11, 6, 8, 16] ผลลัพธ์จะเป็น 14 เนื่องจากเราสามารถข้ามงานแรกและงานสุดท้ายได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- n :=ขนาดของ nums
- table :=สร้างเมทริกซ์ขนาด n x 2 แล้วเติมด้วย 0
- ตาราง[0, 0] :=0
- ตาราง[0, 1] :=nums[0]
- สำหรับฉันในช่วง 1 ถึง n - 1 ทำ
- table[i, 0] :=table[i - 1, 1]
- table[i, 1] =(ค่าต่ำสุดของ table[i - 1, 0] และ table[i - 1][1]) + nums[i]
- คืนค่าต่ำสุดของแถวตาราง [n - 1]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
class Solution: def solve(self, nums): n = len(nums) table = [[0] * 2 for _ in range(n)] table[0][0] = 0 table[0][1] = nums[0] for i in range(1, n): table[i][0] = table[i - 1][1] table[i][1] = min(table[i - 1][0], table[i - 1][1]) + nums[i] return min(table[n - 1]) ob = Solution() nums = [11, 6, 8, 16] print(ob.solve(nums))
อินพุต
[11, 6, 8, 16]
ผลลัพธ์
14
