[
dp
]
Leetcode 1269. Number of Ways to Stay in the Same Place After Some Steps
Problem statement
https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/
Solution
Just do dp with state (index, steps done)
. Note, that on each step we can have 3
possible options, and also that it does no matter that m
be quite big, we never need to traverse more than half of n
.
Complexity
Time complexity is O(n*min(n, m))
, where n = steps
and m = arrLen
Code
class Solution:
def numWays(self, steps, arrLen):
@lru_cache(None)
def dp(ind, s):
if not 0 <= ind < arrLen: return 0
if s == 0: return ind == 0
return (dp(ind-1, s-1) + dp(ind, s-1) + dp(ind+1, s-1)) % MOD
MOD = 10**9 + 7
return dp(0, steps)