A bike is located at the top-left corner of a m x n matrix .
The bike can only move either down or right at any point in time. The bike is trying to reach the bottom-right corner of the matrix.
List the number of unique paths possible.
Example 1: Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right
Example 2: Input: m = 7, n = 3 Output: 28
The solution to this problem can be done in Dynamic Programming.
The fundamental concept too understand is, when you arrive at a point there are only 2 possibilities:
- Arriving from above. [moving down from the previous point]
- Arriving from left. [moving right from the previous point].
Let’s analyze by taking a 4 x 4 matrix as an example. It will contain 16 elements in total.
When you are at arr[0][0] position, you can move right to arr[0][1], and from arr[0][1] you can move to right arr[0][2].
Then when you are at arr[0][0] position, you can move down to arr[1][0], and from arr [2][0] you can move down to arr[3][0].
Initial value will be as shown below
So when you come to arr[1][1], you can reach there by 2 ways from top arr[0][1] or from left arr[1][0]. Hence the value will be 2.
From the above we can come to a conclusion for the below equation:
Paths[i][j] = Paths[i - 1][j] + Paths[i][j - 1]
By using the above formula, we can get the final result matrix as below:
1 1 1 1 1 2 3 4 1 3 6 10 1 4 10 20
Finally, we return the value got at the last element i.e. 20.
Solution in C++
/* * File : unique_paths.cpp * Author : ajay.thousand@gmail.com * Copyright: @ prodevelopertutorial.com */ #include<iostream> #include<vector> using namespace std; int get_unique_paths(int m, int n) { int path [m] [n]; // Base condition // initialize first row to 1 for (int j = 0; j < n; ++j) { path[0][j] = 1; } // Base condition // initialize first column to 1 for (int j = 0; j < n; ++j) { path[j][0] = 1; } // apply the formula Paths[i][j] = Paths[i - 1][j] + Paths[i][j - 1] for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) path[i][j] = path[i - 1][j] + path[i][j - 1]; for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ cout << path[i][j] <<" "; } cout<<endl; } return path[m - 1][n - 1]; } int main() { int m = 4; int n = 4; int result = get_unique_paths(m, n); cout<<"The number of unique paths for a "<<m <<" x "<< n<<" matrix is = "<< result<<endl; return 0; }
Output:
The number of unique paths for a 4 x 4 matrix is = 20
No Responses