BinarySearch 0483 Skip Tasks to Minimize Work

Problem statement

https://binarysearch.com/problems/Skip-Tasks-to-Minimize-Work/

Solution

Variation of Leetcode 0198. House Robber, but return sum(nums) - dp2.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, nums):
        dp1, dp2 = 0, 0
        for num in nums:
            dp1, dp2 = dp2, max(dp1 + num, dp2)          
        return sum(nums) - dp2