ways are you still at index 0

Q: https://leetcode.com/discuss/interview-question/416381/Google-Phone-Interview-Question-DP

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

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        # init, f(n, h), f[i][j], 状态: i step at idx j.
        if arrLen > steps:
            arrLen = steps//2 + 1
        w = arrLen
        n = steps
        MOD = 10**9 + 7
        f = [[0] * (w + 1) for _ in range(n + 1)]
        f[0][1] = 1

        for i in range(1, n + 1):
            for j in range(1, w + 1):
                f[i][j] += f[i - 1][j]
                if j > 1:
                    f[i][j] += f[i - 1][j - 1]
                if j < w:
                    f[i][j] += f[i - 1][j + 1]
                f[i][j] %= MOD
        return f[n][1]

# ...x.
# .....
# x.
# ..
# 最后一步 last step: from left, from right, stay.
# 注意 0, w - 1 的时候, 左右越界情况.

o = Solution()
ans = o.BackWays(w=3, n = 3)
ans = o.BackWays(w=5, n = 12)
print(ans)