BinarySearch 0495 Minimum Sum Subsequence

Problem statement

https://binarysearch.com/problems/Minimum-Sum-Subsequence/

Solution

Classical dp problem, where dp[i] means that we process elements upto i and take the last element.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = min(dp[i - 1], dp[i - 2], dp[i - 3]) + nums[i]

        return min(dp[-3:])