Given the following problem:

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]

Output: True

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]

Output: False

Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

I am trying to come up with a recursive solution. This is what I have so far. I am not looking for the optimal solution. I am just trying to solve using recursion for now. If n[i] is 0 I want the loop to go back to the previous loop and continue recursing, but I can't figure out how to do it.

def jumpGame(self, n: []) -> bool:
    if len(n) < 2:
        return True
    for i in range(len(n)):                      
        for j in range(1, n[i] 1):
            next = i   j
            return self.jumpGame(n[next:])
    return False

CodePudding user response：

When considering recursive solutions, the first thing you should consider is the 'base case', followed by the 'recursive case'. The base case is just 'what is the smallest form of this problem for which I can determine an answer', and the recursive is 'can I get from some form n of this problem to some form n - 1'.

That's a bit pedantic, but lets apply it to your situation. What is the base case? That case is if you have a list of length 1. If you have a list of length 0, there is no last index and you can return false. That would simply be:

if len(ls) == 0:
  return False
if len(ls) == 1:
  return True

Since we don't care what is in the last index, only at arriving at the last index, we know these if statements handle our base case.

Now for the recursive step. Assuming you have a list of length n, we must consider how to reduce the size of the problem. This is by making a 'jump', and we know that we can make a jump equal to a length up to the value of the current index. Then we just need to test each of these lengths. If any of them return True, we succeed.

any(jump_game(n[jump:] for jump in range(1, n[0]   1)))

There are two mechanisms we are using here to make this easy. any takes in a sequence and quits as soon as one value is True, returning True. If none of them are true, it will return False. The second is a list slice, n[jump:] which takes a slice of a list from the index jump to the end. This might result in an empty list.

Putting this together we get:

def jump_game(n: list) -> bool:
  # Base cases
  if len(n) == 0:
    return False
  if len(n) == 1:
    return True
  # Recursive case
  return any(jump_game(n[jump:]) for jump in range(1, n[0]   1))

The results:

>>> jump_game([2,3,1,1,4])
True
>>> jump_game([3,2,1,0,1])
False
>>> jump_game([])
False
>>> jump_game([1])
True

I'm trying to lay out the rigorous approach here, because I think it helps to clarify where recursion goes wrong. In your recursive case you do need to iterate through your options - but that is only one loop, not the two you have. In your solution, in each recursion, you're iterating (for i in range(len(n))) through the entire list. So, you're really hiding an iterative solution inside a recursive one. Further, your base case is wrong, because a list of length 0 is considered a valid solution - but in fact, only a list of length 1 should return a True result.

What you should focus on for recursion is, again, solving the smallest possible form(s) of the problem. Here, it is if the list is one or zero length long. Then, you need to step each other possible size of the problem (length of the list) to a base case. We know we can do that by examining the first element, and choosing to jump anywhere up to that value. This gives us our options. We try each in turn until a solution is found - or until the space is exhausted and we can confidently say there is no solution.

CodePudding user response：

To do that, you need to return self.jumpGame(n[next:]) only if it is True, and not if it is False. This way, you return from your solution only if you acctually have a way - otherwise, you keep trying. (Currently, you return always, from this statement, regardless of the value).

As a side note, this problem is probably a good example for Dynamic Programming, if you later on want to improve your solution :)

Good luck!

CodePudding user response：

If you want to do recursively and you said no need to be optimal ( so not memoized ), you could go with the below method. You don't need nested loops. Also no need to explore all paths, you could optimize by looking at the step that you are going to checking i (jump) < n

def jumpGame(a, i):
  if i > len(a) - 1:
    return False
  if i == len(a) - 1:
    return True
  reached = False
  for j in range(1, a[i]   1):
    if i   j < len(a):
      reached = jumpGame(a, i   j)
    if reached:
      return True
  return reached

print(jumpGame([2, 3, 1, 1, 4], 0))
print(jumpGame([3,2,1,0,4], 0))

True
False