โปรแกรมหาผลรวม subsequence ต่ำสุดโดยเลือกอย่างน้อย 1 จาก 3 ติดกันใน Python

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

ตัวอย่าง: nums = [2, 3, 4, 5, 6, 7] ผลลัพธ์คือ 7 เลือก 2 และ 5

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

1. n = len(nums)
2. กรณีฐาน: n=0 คืน 0, n=1 คืน nums[0], n=2 คืน min(nums[0], nums[1])
3. สร้าง table ขนาด n เติม 0
4. table[0] = nums[0], table[1] = nums[1], table[2] = nums[2]
5. สำหรับ i จาก 3 ถึง n-1: table[i] = nums[i] + min(table[i-3], table[i-2], table[i-1])
6. คืนค่า min(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