Problem statement

https://binarysearch.com/problems/Hop-Cost/

Solution 1

We can use dp with states (position in nums, index of nums (0 or 1)). Then on each step we can either jump upto dist indexes and change/not change array.

Complexity

It is O(n * dist) for time and space.

Code

class Solution:
    def solve(self, nums0, nums1, dist, cost):
        nums = [nums0, nums1]
        n = len(nums0)

        @lru_cache(None)
        def dp(pos, idx):
            num = nums[idx][pos]
            if pos == n - 1: return num

            ans = float("inf")
            for pos2 in range(pos + 1, min(n, pos + dist + 1)):
                ans = min(ans, num + dp(pos2, 0) + cost * idx)
                ans = min(ans, num + dp(pos2, 1) + cost * (1 - idx))

            return ans

        return min(dp(0, 0), dp(0, 1))

Solution 2

There is also better solution, using monotonic deque! The idea is similar to 1696. Jump Game VI, but here we need to keep two deques.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums0, nums1, k, cost):
        nums = [nums0, nums1]
        n = len(nums0)

        deq1, deq2 = deque([0]), deque([0])

        for i in range(1, n):
            while deq1 and deq1[0] < i - k: deq1.popleft()
            while deq2 and deq2[0] < i - k: deq2.popleft()
            nums[0][i] += min(nums[0][deq1[0]], nums[1][deq2[0]] + cost)
            nums[1][i] += min(nums[1][deq2[0]], nums[0][deq1[0]] + cost)

            while deq1 and nums[0][i] <= nums[0][deq1[-1]]: deq1.pop()
            deq1.append(i)
            while deq2 and nums[1][i] <= nums[1][deq2[-1]]: deq2.pop()
            deq2.append(i)
            
        return min(nums[0][-1], nums[1][-1])