Chương trình tìm điểm cộng thêm lớn nhất bằng cách xóa số trong Python

Mô tả bài toán

Cho danh sách nums. Mỗi phép toán: chọn một số (không phải đầu/cuối), xóa nó và cộng điểm bằng tổng của nó và hai số lân cận. Lặp lại nhiều lần tùy thích. Tìm điểm tối đa.

Ví dụ: nums = [2, 3, 4, 5, 6] → đầu ra 39 (chọn 5: 4+5+6=15, mảng thành [2,3,4,6]; chọn 4: 3+4+6=13; chọn 3: 2+3+6=11; tổng=39).

Giải thuật (Quy hoạch động khoảng - Interval DP)

1. n = len(nums). Nếu n < 3 trả về 0.
2. Khởi tạo mảng 2D dp kích thước (n+1) x (n+1).
3. Với độ dài len từ 3 đến n:
   • Với i từ 1 đến n-len+1:
     • r = i + len - 1.
     • ans = 0.
     • Với k từ i+1 đến r-1:
       • curr = dp[i][k] + dp[k][r] + nums[k-1].
       • Cập nhật ans = max(ans, curr).
     • ans += nums[i-1] + nums[r-1].
     • dp[i][r] = ans.
4. Trả về dp[1][n].

Ví dụ mã (C++ chuyển thể sang Python)

class Solution:
    def solve(self, nums):
        n = len(nums)
        if n < 3:
            return 0
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for length in range(3, n + 1):
            for i in range(1, n - length + 2):
                r = i + length - 1
                ans = 0
                for k in range(i + 1, r):
                    curr = dp[i][k] + dp[k][r] + nums[k - 1]
                    if curr > ans:
                        ans = curr
                ans += nums[i - 1] + nums[r - 1]
                dp[i][r] = ans
        return dp[1][n]

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

Đầu vào

[2, 3, 4, 5, 6]

Đầu ra

39