Walmart Interview Question Solve using DP

Given an M X N matrix with your initial position at the top-left cell, find the number of possible unique paths to reach the bottom-right cell of the matrix from the initial position.

Note: Possible moves can be either down or right at any point in time, i.e., we can move to matrix[i+1][j] or matrix[i][j+1] from matrix[i][j].

Recursive Solution for Above Question

def solution(m,n):
    if m==1 or n==1:
        return 1
    return solution(m-1,n)+solution(m,n-1)
print(solution(3,4))

Using Recursive Solution let’s find Dp solution for that,

def solution(m,n):
    temp=[[0 for i in range(m)] for j in range(n)]
    for i in range(m):
        temp[i][0]=1
    for j in range(n):
        temp[0][j]=1
    for i in range(1,m):
        for j in range(n):
            temp[i][j]=temp[i-1][j]+temp[i][j-1]
    return temp[m-1][n-1]