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)

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):
for j in range(n):
for i in range(1,m):
for j in range(n):
return temp[m-1][n-1]