Problem: A robot is located at the top-left corner of a m x n grid.
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 .
How many possible unique paths are there?
Approach 1(Recursion):
Let NumberOfPaths(m, n) be the count of paths to reach row number m and column number n in the matrix, NumberOfPaths(m, n) can be recursively written as following.
/ Returns count of possible paths to reach cell at row number m and column // number n from the topmost leftmost cell (cell at 1, 1) int numberOfPaths(int m, int n) { // If either given row number is first or given column number is first if (m == 1 || n == 1) return 1; // If diagonal movements are allowed then the last addition // is required. return numberOfPaths(m-1, n) + numberOfPaths(m, n-1); // + numberOfPaths(m-1,n-1); }
The time complexity of above recursive solution is exponential.
Approach 2(Dynamic Programming):
This problem has both properties of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array count[][] in bottom up manner using the above recursive formula.
int numberOfPaths(int m, int n) { // Create a 2D table to store results of subproblems int count[m][n]; // Count of paths to reach any cell in first column is 1 for (int i = 0; i < m; i++) count[i][0] = 1; // Count of paths to reach any cell in first column is 1 for (int j = 0; j < n; j++) count[0][j] = 1; <strong> // Calculate count of paths for other cells in bottom-up manner using // the recursive solution for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) // By uncommenting the last part of the code calculates the total // possible paths if the diagonal Movements are allowed count[i][j] = count[i-1][j] + count[i][j-1]; //+ count[i-1][j-1]; } return count[m-1][n-1]; }
Time complexity of the above dynamic programming solution is O(mn).
Note: Count can also be calculated using the formula (m-1 + n-1)!/(m-1)!(n-1)!.
See this for explanation of above formulae.
where should i code the printf statement to get the coordinates of every move i.e path
can you solve this
A robot is located at the bottom-left corner of a grid (m*n). The robot can only move either up (north) or right(east) each time. The robot is trying to reach the top -right corner of the grid How many possible unique paths are there?ALSO, find space and time complexity? (5X5 grid)