bottom_up.py

# dp bottom up
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 1000000007
        if arrLen == 1:return 1
        n = min(251, arrLen)
        dp = [[0 for x in range(steps+1)] for y in range(n)]
        dp[0][0] = 1
        for i in range(1, steps+1):
            dp[0][i] = (dp[0][i-1]+dp[1][i-1]) % MOD
            dp[n-1][i] = (dp[n-1][i-1]+dp[n-2][i-1]) % MOD
            for j in range(1, n-1):
                dp[j][i] = (dp[j][i-1]+dp[j-1][i-1]+dp[j+1][i-1]) % MOD
        return dp[0][steps]