## # Problem ## # Solution

First of all, that's a long title 😂

This problem is actually hard if done in DP, but DFS is easier.

### # DFS

fail on LeetCode

There is a similar problem on LintCode but would pass b/c the steps is only upto 15. However, on LeetCode, the DFS solution would fail as steps is upto 500.

Base conditions for DFS recursion:

• pos out of array, return 0
• steps is 0 and return pos==0 (could further be simplified to: if pos==steps: return 1)
• pos>steps, not enough steps to go back to starting point, return 0 (this condition prunes some branches and would avoid TLS at input steps=15, arrLen=8)

If we don't have the condition if pos>steps to eliminate branches, would TLS on input steps=15, arrLen=8.

Complexity:

• time: where n is steps
• space: (implicit stack space is the max width of tree)
def numWays(self, steps: int, arrLen: int) -> int:
MOD = 10**9 + 7

def dfs(steps, pos) -> int:
if pos<0 or pos>=arrLen:
return 0
if steps==0:
return pos==0
# can't get back
if pos>steps:
return 0
return (dfs(steps-1, pos) + dfs(steps-1, pos-1) + dfs(steps-1, pos+1))%MOD

return dfs(steps,0)


### # Recursive DP - Cheating

Basically the same as DFS, but cache the calculated values using decorator lru_cache in functools to store some branches' result.

Import:

from functools import lru_cache


Use:

@lru_cache(None)
def dfs(steps, pos) -> int:
# same as before


### # Recursive DP (REDO)

C++ https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/discuss/436117/C%2B%2B-Recursive-DP-(Memoization)

Python https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/discuss/436677/Python-DP

Last Updated: 4/6/2020, 4:15:22 PM