A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid . marked ‘end' in the diagram below.How many possible unique paths are there?
I posted the solution with post because i was aware of such problem earlier :)
Basic Solution,Approach,Algoriothms Using BackTracing
Start form top left corner (say we are at position 1,1 in starting deonted by row=r,column=c (e.g. r=1, c=1 initially) & then will will keep moving untill reach when r=m and c=n e.g. bottom-left corner) writing code for this is simple.
int backtrack(int r, int c, int m, int n) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;
return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n);
}
but as normal backtracking problems it inovolves repeated calculations
so is very inefficient in the sense that it recalculates the same solutio n over patah again & again. so we need to use a dynamic programming (DP) technique called memoization akso called top down approach.
const int M_MAX = 10;
const int N_MAX = 10;
int backtrack(int r, int c, int m, int n, int mat[][N_MAX+2]) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;
if (mat[r+1][c] == -1)
mat[r+1][c] = backtrack(r+1, c, m, n, mat);
if (mat[r][c+1] == -1)
mat[r][c+1] = backtrack(r, c+1, m, n, mat);
return mat[r+1][c] + mat[r][c+1];
}
int bt(int m, int n) {
int mat[M_MAX][N_MAX];
memset(mat, -1, sizeof(mat));
return backtrack(1, 1, m, n, mat);
}
Time Complexity O(M+N)
Space Complexity O(M*N)
Bottom-Up Dynamic Programming More Efficient
As we know The total unique paths at above matrix (r,c) is equal to the sum of total unique paths from matrix to the right (r,c+1) and the matrix below (r+1,c).
(For clarity, we will solve this part assuming an X*Y Matrix)
Each path has (X-1)+(Y-1) steps. Imagine the following paths:
X X Y Y X (move right -> right -> down -> down -> right)
X Y X Y X (move right -> down -> right -> down -> right)
...& so on
Each path can be fully represented by the moves at which we move
right. That is, if I were to ask you which path you took, you could
simply say “I moved right on step 3 and 4.”
Since you must always move right X-1 times, and you have X-1 + Y-1
total steps, you have to pick X-1 times to move right out of X-1+Y-1
choices. Thus, there are C(X-1, X-1+Y-1) paths (e.g., X-1+Y-1 choose
X-1):
(X-1 + Y-1)! / ((X-1)! * (Y-1)!)..
const int M_MAX = 100;
const int N_MAX = 100;
int dp(int m, int n) {
int mat[M_MAX][N_MAX] = {0};
mat[m][n+1] = 1;
for (int r = m; r >= 1; r--)
for (int c = n; c >= 1; c--)
mat[r][c] = mat[r+1][c] + mat[r][c+1];
return mat[1][1];
}
Lets Assume you have M×N sample matrix or grid. so it doen't matter how you traverse the grids, you always traverse a total of M steps. To be more exact, you always have to choose M-N steps to the right (R) and N steps to the bottom (B). Therefore, the problem can be transformed to a question of how many ways can you choose M-N R‘s and N B‘s in these M+N-2 steps. The answer is C(M,N) (or C(M,M-N)). Therefore, the general solution for a m x n grid is C(m+n-2, m-1) & this is our answer.
Time Complexity O(M*N)
Space Complexity O(M*N)
Follow Up: Using Above We Have Only Calculated the number of paths can we print those path as well if yes what will be time complexity.
