A Maniacal Walk- Google Top Interview Questions

                        Solution in C++ :

int solve(int length, int n) {
    if (!length) return 0;

    vector<int> dp(length);

    // 1 way to be at the index 0 with 0 steps
    dp[0] = 1;
    const int MOD = 1e9 + 7;

    // calculate answer for each steps
    while (n--) {
        auto dpc = dp;
        for (int i = 0; i < length; ++i) {
            if (i > 0) dpc[i - 1] = (dpc[i - 1] + dp[i]) % MOD;
            if (i < length - 1) dpc[i + 1] = (dpc[i + 1] + dp[i]) % MOD;
        }
        dp = dpc;
    }

    return dp[0] % MOD;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int length, int n) {
        if (n == 0)
            return 1;

        int[] dp1 = new int[length];
        int[] dp2 = new int[length];

        final int MOD = (int) 1e9 + 7;

        dp1[0] = 1;

        for (int left = 1; left <= n; left++) {
            for (int i = 0; i < length; i++) {
                dp2[i] = ((dp1[i] + (i - 1 >= 0 ? dp1[i - 1] : 0)) % MOD
                             + (i + 1 < length ? dp1[i + 1] : 0))
                    % MOD;
            }

            for (int i = 0; i < length; i++) {
                dp1[i] = dp2[i];
            }
        }

        return dp1[0];
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, length, n):
        len = min(n + 1, length)
        start = [0] * len
        start[0] = 1
        for i in range(n):
            new = [0] * len
            for j in range(len):
                if j != 0 and j != len - 1:
                    new[j] = start[j - 1] + start[j] + start[j + 1]
                elif j == 0:
                    new[j] = start[j] + start[j + 1]
                else:
                    new[j] = start[j - 1] + start[j]
            start = new
        return start[0] % (10 ** 9 + 7)