Chương trình tìm tổng các phần tử không kề nhau trong danh sách vòng trong Python

Mô tả bài toán

Cho danh sách nums biểu diễn danh sách vòng (phần tử đầu và cuối coi là kề nhau). Tìm tổng lớn nhất của các phần tử không kề nhau.

Ví dụ: nums = [10, 3, 4, 8] → đầu ra 14 (chọn 10 và 4; không thể chọn 10 và 8 vì kề nhau).

Giải thuật (Quy hoạch động trên 2 trường hợp)

1. Tách thành 2 bài toán tuyến tính: loại bỏ phần tử cuối (nums1 = nums[:-1]) và loại bỏ phần tử đầu (nums2 = nums[1:]).
2. Định nghĩa hàm f(i) cho nums1: max(nums1[i] + f(i+2), f(i+1)).
3. Định nghĩa hàm g(j) cho nums2 tương tự.
4. Trả về max(f(0), g(0)).

Ví dụ mã Python

class Solution:
    def solve(self, nums):
        n = len(nums)
        nums1 = nums[: n - 1]
        nums2 = nums[1:]
        def f(i):
            if i >= len(nums1):
                return 0
            return max(nums1[i] + f(i + 2), f(i + 1))
        def g(j):
            if j >= len(nums2):
                return 0
            return max(nums2[j] + g(j + 2), g(j + 1))
        return max(f(0), g(0))

ob = Solution()
nums = [10, 3, 4, 8]
print(ob.solve(nums))

Đầu vào

[10, 3, 4, 8]

Đầu ra

14