TARGET DECK: Leetcode FILE TAGS: Hard
Intuition
- On each step, you are tasked with going left, right, or staying in the same position.
- Therefore, recursively, you can simulate each possible way of going left, right, or staying.
- If you end up at step 0 after exhausting all your steps, then count that as one way of getting to and from to step 0.
- Otherwise, discard that way of stepping.
Complexity
Runtime
$
Space
$
Code
class Solution:
def numWays(self, steps: int, arrLen: int) -> int:
dp = {}
def r(i, s):
if not (0 <= i < arrLen) or s < 0:
return 0
if s == 0 and i == 0:
return 1
if (i, s) in dp:
return dp[(i, s)]
dp[(i, s)] = r(i, s - 1) + r(i - 1, s - 1) + r(i + 1, s - 1)
return dp[(i, s)] % (10 ** 9 + 7)
return r(0, steps) % (10 ** 9 + 7)Notes
Cards
START Basic Front: Number Of Ways To Stay In The Same Place After Some Steps Back: Stay, go left, or go right, decrementing your number of steps by one each time.
END