โปรแกรมหาเวลาขั้นต่ำในการทำทุกงานใน Python

มีรายการ nums เวลาแต่ละงาน ข้ามงานติดกันไม่ได้ (ต้องทำงานสลับกัน) หาเวลาน้อยที่สุดทำทั้งหมด

เช่น nums=[11,6,8,16] ให้ 14 (ข้ามงานแรกและสุดท้าย ทำ 6+8)

ขั้นตอนการแก้ปัญหา

• DP: table[i][0] = เวลาน้อยสุดถึง i ถ้าข้ามงาน i, table[i][1] = ทำงาน i
• table[0][0]=0, table[0][1]=nums[0]
• table[i][0] = table[i-1][1] (ข้าม i ต้องทำ i-1)
• table[i][1] = min(table[i-1][0], table[i-1][1]) + nums[i]
• คืนค่า min(table[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