โปรแกรมหาจำนวนการรวมตัวเลขติดกันเพื่อให้ลิสต์ไม่เพิ่ม (non-increasing) ใน Python

คำอธิบายโจทย์

ให้รายการ nums Operation: รวม 2 ตัวติดกันเป็นผลรวม หา operations น้อยที่สุดทำให้ list กลายเป็น non-increasing (แต่ละตัว ≥ ตัวถัดไป)

ตัวอย่าง

nums = [2, 6, 4, 10, 2] → 2 (รวม [2,6]→8 ได้ [8,4,10,2] แล้วรวม [8,4]→12 ได้ [12,10,2])

วิธีแก้ปัญหา

DP แบบ Greedy จากท้ายมาหน้า:

1. เพิ่ม -inf ท้าย list เป็น sentinel
2. dp[i] = operations น้อยที่สุดจาก i ถึงสุด
3. arr[i] = ค่ารวมของกลุ่มเริ่มที่ i (หลัง merge แล้ว)
4. จากท้ายมาหน้า: รวม nums[i] กับตัวถัดไปจนกว่า arr[i] ≥ arr[i+1]

โค้ด Python

class Solution:
    def solve(self, nums):
        if not nums:
            return 0
        nums.append(float("-inf"))
        N = len(nums)
        dp = [0] * N
        arr = [0] * N
        arr[-1] = nums[-1]
        arr[-2] = nums[-2]
        for i in range(N - 3, -1, -1):
            j = i
            x = nums[j]
            while j < N - 1 and x < arr[j + 1]:
                j += 1
                x += nums[j]
            dp[i] = j - i + dp[j + 1]
            arr[i] = x
        return dp[0]

ob = Solution()
nums = [2, 6, 4, 10, 2]
print(ob.solve(nums))

อินพุต

[2, 6, 4, 10, 2]

เอาต์พุต

2