**Unique Paths in a Grid**
================================
### Problem Statement
Given the dimensions of a grid (`m` x `n`), count the number of unique paths from the top-left corner to the bottom-right corner. The movement is restricted to only right and down directions.
### C++ Code
```cpp
#include <iostream>
#include <vector>
/**
* @brief Counts the number of unique paths in a grid.
*
* @param m The number of rows in the grid.
* @param n The number of columns in the grid.
* @return int The number of unique paths.
*/
int uniquePaths(int m, int n) {
// Create a 2D vector to store the number of unique paths to each cell.
std::vector<std::vector<int>> dp(m, std::vector<int>(n, 1));
// Fill the dp table in a bottom-up manner.
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// The number of unique paths to a cell is the sum of the number of unique paths to the cell above it and the cell to its left.
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
// The number of unique paths to the bottom-right corner is stored in the bottom-right cell of the dp table.
return dp[m - 1][n - 1];
}
int main() {
int m = 3; // Number of rows
int n = 7; // Number of columns
int unique_paths = uniquePaths(m, n);
std::cout << "Number of unique paths in a " << m << "x" << n << " grid: " << unique_paths << std::endl;
return 0;
}
```
### Explanation
* We use dynamic programming to solve this problem.
* The `uniquePaths` function takes the dimensions of the grid (`m` and `n`) as input and returns the number of unique paths.
* We create a 2D vector `dp` of size `m x n` to store the number of unique paths to each cell. We initialize all cells in the first row and first column to 1, since there is only one way to reach each cell in these rows (by moving right or down, respectively).
* We fill the `dp` table in a bottom-up manner. For each cell `(i, j)`, we calculate the number of unique paths to it by adding the number of unique paths to the cell above it (`dp[i - 1][j]`) and the cell to its left (`dp[i][j - 1]`).
* Finally, we return the number of unique paths to the bottom-right corner, which is stored in the bottom-right cell of the `dp` table.
### Time Complexity
* The time complexity of this solution is O(m \* n), where m and n are the dimensions of the grid.
### Space Complexity
* The space complexity of this solution is O(m \* n), which is used to store the `dp` table.
### Example Use Case
* For a 3x7 grid, the output will be 28, indicating that there are 28 unique paths from the top-left corner to the bottom-right corner.
Nume AI CFO
Mini tools
Open**Unique Paths in a Grid** ================================ ### Problem Statement Given the dimensions of a grid (`m` x `n`), count the number of unique paths from the top-left corner to the bottom-right corner. The movement is restricted to only right and down directions. ### C++ Code ```cpp #include <iostream> #include <vector> /** * @brief Counts the number of unique paths in a grid. * * @param m The number of rows in the grid. * @param n The number of columns in the grid. * @return int The number of unique paths. */ int uniquePaths(int m, int n) { // Create a 2D vector to store the number of unique paths to each cell. std::vector<std::vector<int>> dp(m, std::vector<int>(n, 1)); // Fill the dp table in a bottom-up manner. for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { // The number of unique paths to a cell is the sum of the number of unique paths to the cell above it and the cell to its left. dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } // The number of unique paths to the bottom-right corner is stored in the bottom-right cell of the dp table. return dp[m - 1][n - 1]; } int main() { int m = 3; // Number of rows int n = 7; // Number of columns int unique_paths = uniquePaths(m, n); std::cout << "Number of unique paths in a " << m << "x" << n << " grid: " << unique_paths << std::endl; return 0; } ``` ### Explanation * We use dynamic programming to solve this problem. * The `uniquePaths` function takes the dimensions of the grid (`m` and `n`) as input and returns the number of unique paths. * We create a 2D vector `dp` of size `m x n` to store the number of unique paths to each cell. We initialize all cells in the first row and first column to 1, since there is only one way to reach each cell in these rows (by moving right or down, respectively). * We fill the `dp` table in a bottom-up manner. For each cell `(i, j)`, we calculate the number of unique paths to it by adding the number of unique paths to the cell above it (`dp[i - 1][j]`) and the cell to its left (`dp[i][j - 1]`). * Finally, we return the number of unique paths to the bottom-right corner, which is stored in the bottom-right cell of the `dp` table. ### Time Complexity * The time complexity of this solution is O(m \* n), where m and n are the dimensions of the grid. ### Space Complexity * The space complexity of this solution is O(m \* n), which is used to store the `dp` table. ### Example Use Case * For a 3x7 grid, the output will be 28, indicating that there are 28 unique paths from the top-left corner to the bottom-right corner.
