Chương trình tìm tổng cặp nhỏ nhất trong đó khoảng cách không liên tiếp bằng Python

Giả sử chúng ta có một danh sách các số được gọi. Bây giờ chúng ta hãy xem xét bất kỳ cặp chỉ số nào (i, j) trong đó i 1. Sau đó tìm tổng của cặp nhỏ nhất.

Vì vậy, nếu đầu vào là nums =[3, 4, 2, 2, 4], thì đầu ra sẽ là 5, chúng ta có thể chọn giá trị 3 và 2 nên tổng tổng là 5. Chúng ta không thể chọn 2 và 2 vì chúng liền kề và vi phạm ràng buộc j - i> 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums
• min_seen:=nums [0]
• ans:=inf
• đối với tôi trong phạm vi từ 2 đến n - 1, thực hiện
  • ans:=tối thiểu ans và (min_seen + nums [i])
  • min_seen:=tối thiểu min_seen và nums [i - 1]
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[3, 4, 2, 2, 4]

Đầu ra

5