Leetcode 1757 Solution

This article provides solution to leetcode question 1757 (minimum-jumps-to-reach-home)
Categories:
Tags:
Access this page by simply typing in "lcs 1757" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-jumps-to-reach-home

Solution

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        m = {}

        def f(n, s):
            nonlocal a
            nonlocal b
            nonlocal m

            if n == 0:
                return 0

            if n > x + 10 * b or n < 0 or n in forbidden:
                return None

            key = (n, s)
            if key in m:
                return m[key]

            m[key] = None

            candidates = []

            if s == 0:
                candidate = f(n + b, 1)

                if candidate is not None:
                	candidates.append(candidate)
            elif s == 1:
                candidate1 = f(n - a, 0)
                candidate2 = f(n - a, 1)

                if candidate1 is not None:
                    candidates.append(candidate1)
                if candidate2 is not None:
                    candidates.append(candidate2)

            m[key] = min(candidates) + 1 if candidates else None
            return m[key]

        candidates = []
        candidate1 = f(x, 0)
        if candidate1 is not None:
            candidates.append(candidate1)
        candidate2 = f(x, 1)
        if candidate2 is not None:
            candidates.append(candidate2)

        return min(candidates) if candidates else -1