Chương trình tìm số phép toán để biến danh sách thành dãy không tăng trong Python

Cho danh sách nums. Phép toán: gộp hai phần tử liên tiếp thành tổng của chúng. Tìm số phép toán tối thiểu để danh sách trở thành không tăng (non-increasing).

Ví dụ: nums = [2, 6, 4, 10, 2] → 2 (gộp [2,6]→[8,4,10,2], rồi [8,4]→[12,10,2]).

Giải pháp

DP từ phải sang trái:

• Thêm -inf vào cuối nums
• dp[i] = số phép gộp tối thiểu từ i đến cuối
• arr[i] = giá trị của khối bắt đầu tại i sau khi gộp tối ưu
• Duyệt i từ n-3 về 0: mở rộng j từ i, cộng dồn x = nums[j] cho đến khi x >= arr[j+1]
• dp[i] = j - i + dp[j+1], arr[i] = x

Ví dụ minh họa

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

Đầu vào

[2, 6, 4, 10, 2]

Đầu ra

2