Walmart Interview Question Solve using DP

sohesh doshi
1 min readJan 5, 2020

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]

--

--