Chương trình tìm tổng nhỏ nhất của dãy con lấy ít nhất một phần tử từ 3 phần tử liên tiếp trong Python

Mô tả bài toán

Cho danh sách nums. Tìm tổng nhỏ nhất của một dãy con sao cho với mọi nhóm 3 phần tử liên tiếp, ít nhất một phần tử được chọn. Nếu độ dài < 3, vẫn phải chọn ít nhất một phần tử.

Ví dụ: nums = [2, 3, 4, 5, 6, 7] → đầu ra 7 (chọn 2 và 5).

Giải thuật (Quy hoạch động)

1. n = len(nums). Xử lý các trường hợp cơ sở n = 0,1,2.
2. Khởi tạo mảng table kích thước n toàn 0.
3. table[0] = nums[0], table[1] = nums[1], table[2] = nums[2].
4. Với i từ 3 đến n-1: table[i] = nums[i] + min(table[i-3], table[i-2], table[i-1]).
5. Kết quả = min(table[n-1], table[n-2], table[n-3]).

Ví dụ mã Python

class Solution:
    def solve(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return min(nums[0], nums[1])
        table = [0] * n
        table[0] = nums[0]
        table[1] = nums[1]
        table[2] = nums[2]
        for i in range(3, n):
            table[i] = nums[i] + min(table[i - 3], table[i - 2], table[i - 1])
        res = min(table[n - 1], table[n - 2], table[n - 3])
        return res

ob = Solution()
nums = [2, 3, 4, 5, 6, 7]
print(ob.solve(nums))

Đầu vào

[2, 3, 4, 5, 6, 7]

Đầu ra

7