Number of Ways to Stay in the Same Place After Some Steps

Solution

First of all, that's a long title 😂

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

Let $n$ be the number of steps.

DFS

fail on LeetCode

There is a similar problem on LintCode (opens new window) but would pass b/c the steps is only upto 15. However, on LeetCode, the DFS solution would fail when 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: $O(3^n)$
space: $O(3^n)$ (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