Chương trình tìm thời gian tối thiểu hoàn thành tất cả nhiệm vụ bằng Python

Cho danh sách nums thời gian mỗi nhiệm vụ. Có thể bỏ qua nhiệm vụ nhưng không được bỏ 2 nhiệm vụ liên tiếp. Tìm tổng thời gian tối thiểu.

Ví dụ: [11,6,8,16] → 14 (bỏ nhiệm vụ 1 và 4).

Giải thuật

• Quy hoạch động: table[i][0] = min time đến i nếu bỏ nhiệm vụ i, table[i][1] = min time nếu làm nhiệm vụ i.
• Chuyển trạng thái: table[i][0] = table[i-1][1] (bỏ i → phải làm i-1), table[i][1] = min(table[i-1][0], table[i-1][1]) + nums[i].
• Kết quả: min(table[n-1]).

Ví dụ minh họa

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))

Đầu vào

[11, 6, 8, 16]

Đầu ra

14