This problem is directly a DP problem with some optimization.
We define ways to go to a position i at time t as S(t, i). Based on the description of this problem:
S(t, i) = S(t - 1, i - 1) + S(t - 1, i) + S(t - 1, i + 1)
And the initial status is S(0, 0) == 1 and S(0, i) == 1 for any i > 0.
One optimization here is that, for any time t, the maximum i where S(t, i) > 0 is less than t + 1. So we can use it to skip some useless calculation.
class Solution:
def numWays(self, steps: int, arrLen: int) -> int:
ways = [0] * arrLen
ways[0] = 1
mod = (10 ** 9) + 7
for _ in range(steps):
tmp = [0] * arrLen
for i in range(arrLen):
tmp[i] = ways[i]
if i > 0:
tmp[i] += ways[i - 1]
if i < arrLen - 1:
tmp[i] += ways[i + 1]
tmp[i] = tmp[i] % mod
if tmp[i] == 0:
break
ways = tmp
return ways[0]