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

Problem Id: 1269 Difficulty: Hard Tag: Dynamic Programming


Intuition

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.

Solution


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]