โปรแกรมหาผลรวมคู่น้อยที่สุดที่ระยะห่างไม่ติดกันใน Python

สมมติว่าเรามีรายการตัวเลข ให้พิจารณาคู่ดัชนี (i, j) ที่ i < j และ j - i > 1 หาผลรวมคู่ที่น้อยที่สุด

เช่น ถ้าอินพุตคือ nums = [3, 4, 2, 2, 4] ผลลัพธ์จะเป็น 5 สามารถเลือก 3 และ 2 ผลรวม 5 ไม่สามารถเลือก 2 และ 2 เพราะติดกัน違反 j - i > 1

ขั้นตอนการแก้ปัญหา

1. n := ขนาดของ nums
2. min_seen := nums[0], ans := inf
3. สำหรับ i ในช่วง 2 ถึง n-1:
   • ans := min(ans, min_seen + nums[i])
   • min_seen := min(min_seen, nums[i-1])
4. คืนค่า ans

ตัวอย่างการใช้งาน

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

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

อินพุต

[3, 4, 2, 2, 4]

เอาต์พุต

5