Chương trình tìm tổng cặp nhỏ nhất với khoảng cách không liên tiếp Python

Cho mảng nums. Tìm cặp chỉ số (i,j) với i < j và 1 (không liên tiếp) có tổng nhỏ nhất.

Ví dụ: nums=[3,4,2,2,4] → 5 (chọn 3 và 2 tại chỉ số 0 và 2; không chọn 2 và 2 vì liền kề).

Giải thuật (Theo dõi min_seen)

1. min_seen = nums[0], ans = inf
2. Duyệt i từ 2 đến n-1:
   • ans = min(ans, min_seen + nums[i])
   • min_seen = min(min_seen, nums[i-1])
3. Trả về ans

Ví dụ triển khai

def solve(nums):
    n = len(nums)
    min_seen = nums[0]
    ans = float("inf")
    for i in range(2, n):
        ans = min(ans, min_seen + nums[i])
        min_seen = min(min_seen, nums[i-1])
    return ans

print(solve([3, 4, 2, 2, 4]))

Đầu vào

[3, 4, 2, 2, 4]

Đầu ra

5