jump_game_ii

View Source

 1from functools import cache
 2
 3
 4# @leet start
 5class Solution:
 6    def jump(self, nums: list[int]) -> int:
 7        """
 8        This question asks us to find the shortest path from index 0 to the last
 9        index, given an array counting the number of steps we can jump up to.
10
11        We can do this by breaking this problem down into its subsequent cases:
12        1. if we ask for an index to the right of the array, we've cleared it,
13        so we return 0.
14        2. If our current number is 0, we return infinity because we can't reach
15        the end from here.
16        3. Otherwise, we check all of our next positions, which is the range
17        1..nums[i], and return 1 + the minimum of that.
18
19        Finally, we start at the first index and return the number of steps taken.
20        """
21        n = len(nums)
22
23        @cache
24        def dp(i):
25            if i >= n - 1:
26                return 0
27            elif nums[i] == 0:
28                return float("inf")
29            else:
30                return 1 + min(dp(i + x) for x in range(1, nums[i] + 1))
31
32        return dp(0)
33
34
35# @leet end
36
37
38def test():
39    assert 2 + 2 == 4

class Solution: View Source

 6class Solution:
 7    def jump(self, nums: list[int]) -> int:
 8        """
 9        This question asks us to find the shortest path from index 0 to the last
10        index, given an array counting the number of steps we can jump up to.
11
12        We can do this by breaking this problem down into its subsequent cases:
13        1. if we ask for an index to the right of the array, we've cleared it,
14        so we return 0.
15        2. If our current number is 0, we return infinity because we can't reach
16        the end from here.
17        3. Otherwise, we check all of our next positions, which is the range
18        1..nums[i], and return 1 + the minimum of that.
19
20        Finally, we start at the first index and return the number of steps taken.
21        """
22        n = len(nums)
23
24        @cache
25        def dp(i):
26            if i >= n - 1:
27                return 0
28            elif nums[i] == 0:
29                return float("inf")
30            else:
31                return 1 + min(dp(i + x) for x in range(1, nums[i] + 1))
32
33        return dp(0)

def jump(self, nums: list[int]) -> int: View Source

 7    def jump(self, nums: list[int]) -> int:
 8        """
 9        This question asks us to find the shortest path from index 0 to the last
10        index, given an array counting the number of steps we can jump up to.
11
12        We can do this by breaking this problem down into its subsequent cases:
13        1. if we ask for an index to the right of the array, we've cleared it,
14        so we return 0.
15        2. If our current number is 0, we return infinity because we can't reach
16        the end from here.
17        3. Otherwise, we check all of our next positions, which is the range
18        1..nums[i], and return 1 + the minimum of that.
19
20        Finally, we start at the first index and return the number of steps taken.
21        """
22        n = len(nums)
23
24        @cache
25        def dp(i):
26            if i >= n - 1:
27                return 0
28            elif nums[i] == 0:
29                return float("inf")
30            else:
31                return 1 + min(dp(i + x) for x in range(1, nums[i] + 1))
32
33        return dp(0)

This question asks us to find the shortest path from index 0 to the last index, given an array counting the number of steps we can jump up to.

We can do this by breaking this problem down into its subsequent cases:

if we ask for an index to the right of the array, we've cleared it, so we return 0.
If our current number is 0, we return infinity because we can't reach the end from here.
Otherwise, we check all of our next positions, which is the range 1..nums[i], and return 1 + the minimum of that.

Finally, we start at the first index and return the number of steps taken.

def test(): View Source

39def test():
40    assert 2 + 2 == 4