bfs.py

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10**9 + 7
        POS = min(steps//2+1, arrLen)
        dp = collections.defaultdict(int)
        def bfs(pos, step):
            cur_level = {(pos, step)}
            dp[(pos, step)] = 1
            while cur_level:
                nxt_level = set()
                for pos, step in cur_level:
                    #'left':-1, 'stay':0, 'right':1
                    for action in [-1, 0, 1]:
                        if 0<=pos+action<POS and step+1<=steps:
                            dp[(pos+action, step+1)] +=  dp[(pos, step)] % MOD
                            nxt_level.add((pos+action, step+1))
                cur_level = nxt_level
                        
        bfs(0, 0)
        return dp[(0, steps)]%MOD