1269

class Solution {
public:
    int dp[501][501];
    int numWays(int steps, int arrlen) {
        memset(dp, -1, sizeof dp);
        return dfs(steps, 0, steps, arrlen);
    }

    int dfs(int curSteps, int pos, int steps, int len){
        if(pos<0 || pos>=len || curSteps < 0) return 0;
        if(curSteps == 0 && pos == 0) return 1;
        if(dp[pos][curSteps] != -1) return dp[pos][curSteps];

        long long int paths = 0, mod=int(1e9)+7;
        paths += dfs(curSteps-1, pos+1, steps, len)%mod;
        paths += dfs(curSteps-1, pos-1, steps, len)%mod;
        paths += dfs(curSteps-1, pos, steps, len)%mod;
        return dp[pos][curSteps] = paths%mod;
    }
};

----------------------

class Solution {
public:
    int numWays(int steps, int arrLen) {
        int sz = min(steps/2+1, arrLen);
        vector<int> v1(sz+2), v2(sz + 2);
        v1[1] = 1;
        while(steps--){
            for(auto i = 1; i <= sz; ++i)
                v2[i] = ((long)v1[i] + v1[i - 1] + v1[i + 1]) % 1000000007;
            swap(v1, v2);
        }
        return v1[1];
    }
};