Chương trình tìm dãy con tổng nhỏ nhất bằng cách lấy ít nhất một phần tử từ 3 phần tử liên tiếp trong python

Giả sử chúng ta có một danh sách các số được gọi là num, chúng ta phải tìm một dãy con tổng nhỏ nhất từ ​​danh sách đã cho sao cho ít nhất một số cho tất cả các nhóm ba số liên tiếp được chọn. Nếu độ dài của danh sách đã cho nhỏ hơn 3, một số vẫn nên được chọn.

Vì vậy, nếu đầu vào là nums =[2, 3, 4, 5, 6, 7], thì đầu ra sẽ là 7, vì chúng ta có thể chọn 2 và 5.

Để 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
• nếu n giống 0, thì
  • trả về 0
• nếu n giống 1, thì
  • trả về số [0]
• nếu n giống 2 thì
  • trả về tối thiểu nums [0] và nums [1]
• table:=một danh sách có kích thước n và điền bằng 0
• bảng [0]:=nums [0]
• bảng [1]:=nums [1]
• bảng [2]:=nums [2]
• đối với tôi trong phạm vi từ 3 đến n, thực hiện
  • bảng [i]:=nums [i] + mức tối thiểu của bảng [i - 3], bảng [i - 2] và bảng [i - 1]
• res:=tối thiểu của bảng [n - 1], bảng [n - 2] và bảng [n - 3]
• trả lại res

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

Mã mẫu

class Solution:
   def solve(self, nums):
      n = len(nums)
      if n == 0:
         return 0
      if n == 1:
         return nums[0]
      if n == 2:
         return min(nums[0], nums[1])
      table = [0] * n

      table[0] = nums[0]
      table[1] = nums[1]
      table[2] = nums[2]

      for i in range(3, n):
         table[i] = nums[i] + min(table[i - 3], table[i - 2], table[i - 1])

         res = min(table[n - 1], table[n - 2], table[n - 3])
      return res

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

Đầu vào

[2, 3, 4, 5, 6, 7]

Đầu ra

7