โปรแกรมค้นหาผลรวมขั้นต่ำโดยนำองค์ประกอบอย่างน้อยหนึ่งองค์ประกอบจาก 3 องค์ประกอบติดต่อกันใน python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราต้องหาลำดับผลรวมขั้นต่ำจากรายการที่กำหนด โดยเลือกหมายเลขอย่างน้อยหนึ่งหมายเลขสำหรับกลุ่มตัวเลขสามหมายเลขต่อเนื่องกันทั้งหมด หากความยาวของรายการที่กำหนดน้อยกว่า 3 ควรเลือกตัวเลข

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 3, 4, 5, 6, 7] ผลลัพธ์จะเป็น 7 ตามที่เราเลือกได้ 2 และ 5

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• n :=ขนาดของ nums
• ถ้า n เหมือนกับ 0 แล้ว
  • คืน 0
• ถ้า n เหมือนกับ 1 แล้ว
  • ส่งคืน nums[0]
• ถ้า n เหมือนกับ 2 แล้ว
  • คืนค่าขั้นต่ำของ nums[0] และ nums[1]
• table :=รายการขนาด n และเติม 0
• ตาราง[0] :=nums[0]
• ตาราง[1] :=nums[1]
• ตาราง[2] :=nums[2]
• สำหรับฉันในช่วง 3 ถึง n ทำ
  • table[i] :=nums[i] + ค่าต่ำสุดของ table[i - 3], table[i - 2] และ table[i - 1]
• res :=ขั้นต่ำของ table[n - 1], table[n - 2] และ table[n - 3]
• ผลตอบแทน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

โค้ดตัวอย่าง

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

อินพุต

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

ผลลัพธ์

7