Problem Statement: Unique Paths
You are given an m x n grid. Starting from the top-left corner, you need to find how many unique paths exist to reach the bottom-right corner. You can only move right or down at any point in time.
Write a function to return the number of unique paths.
Example 1:
Input:
m = 3, n = 7
Output:
28
Explanation: There are 28 unique paths to go from the top-left to the bottom-right corner in a 3×7 grid.
Example 2:
Input:
m = 3, n = 2
Output:
3
Explanation: There are 3 unique paths to go from the top-left to the bottom-right corner in a 3×2 grid.
Approach:
The problem can be solved using Dynamic Programming (DP) or Combinatorics.
Approach 1: Dynamic Programming (DP)
- State Definition:
- Let
dp[i][j]represent the number of unique paths to reach the cell(i, j)from the top-left corner(0, 0).
- Let
- State Transition:
- The cell
(i, j)can be reached either from the left(i, j-1)or from above(i-1, j). Hence, the number of unique paths to(i, j)is the sum of paths from these two cells: dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1] - The base cases are:
- If you are in the first row (
i == 0), there is only one way to reach any cell, by moving right. - If you are in the first column (
j == 0), there is only one way to reach any cell, by moving down.
- If you are in the first row (
- The cell
- Space Optimization:
- We can reduce the space complexity by using a 1D array instead of a 2D array, since each row only depends on the previous row.
Approach 2: Combinatorics
- The problem can also be viewed as selecting a path from a grid with
m-1down movements andn-1right movements. - The total number of steps is
(m - 1) + (n - 1)and out of these, we need to choose eitherm-1down steps orn-1right steps. - The number of ways to select the down steps is given by the binomial coefficient: C(m+n−2,m−1)=(m+n−2)!(m−1)!(n−1)!C(m + n – 2, m – 1) = \frac{(m + n – 2)!}{(m – 1)! (n – 1)!}C(m+n−2,m−1)=(m−1)!(n−1)!(m+n−2)!
Code Implementations in Different Languages:
1. C Language (DP Approach):
#include <stdio.h>
int uniquePaths(int m, int n) {
int dp[n];
for (int i = 0; i < n; i++) {
dp[i] = 1; // First row, all cells have 1 way (move right only)
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1]; // Sum of top and left cell values
}
}
return dp[n - 1];
}
int main() {
int m = 3, n = 7;
printf("Unique Paths: %d\n", uniquePaths(m, n)); // Output: 28
return 0;
}
2. C++ Language (DP Approach):
#include <iostream>
#include <vector>
using namespace std;
int uniquePaths(int m, int n) {
vector<int> dp(n, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1]; // Sum of top and left cell values
}
}
return dp[n - 1];
}
int main() {
int m = 3, n = 7;
cout << "Unique Paths: " << uniquePaths(m, n) << endl; // Output: 28
return 0;
}
3. Java (DP Approach):
public class UniquePaths {
public static int uniquePaths(int m, int n) {
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1; // First row, all cells have 1 way (move right only)
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1]; // Sum of top and left cell values
}
}
return dp[n - 1];
}
public static void main(String[] args) {
int m = 3, n = 7;
System.out.println("Unique Paths: " + uniquePaths(m, n)); // Output: 28
}
}
4. Python (DP Approach):
def uniquePaths(m, n):
dp = [1] * n # First row, all cells have 1 way (move right only)
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1] # Sum of top and left cell values
return dp[-1]
# Test case
m, n = 3, 7
print("Unique Paths:", uniquePaths(m, n)) # Output: 28
5. C# (DP Approach):
using System;
class Program {
public static int UniquePaths(int m, int n) {
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1; // First row, all cells have 1 way (move right only)
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1]; // Sum of top and left cell values
}
}
return dp[n - 1];
}
static void Main() {
int m = 3, n = 7;
Console.WriteLine("Unique Paths: " + UniquePaths(m, n)); // Output: 28
}
}
6. JavaScript (DP Approach):
function uniquePaths(m, n) {
let dp = new Array(n).fill(1); // First row, all cells have 1 way (move right only)
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] += dp[j - 1]; // Sum of top and left cell values
}
}
return dp[n - 1];
}
// Test case
let m = 3, n = 7;
console.log("Unique Paths:", uniquePaths(m, n)); // Output: 28
Approach 2: Combinatorics
Using the combinatorics formula, the number of unique paths from the top-left to the bottom-right is given by the binomial coefficient:C(m+n−2,m−1)=(m+n−2)!(m−1)!(n−1)!C(m + n – 2, m – 1) = \frac{(m + n – 2)!}{(m – 1)! (n – 1)!}C(m+n−2,m−1)=(m−1)!(n−1)!(m+n−2)!
Python Code (Combinatorics Approach):
import math
def uniquePaths(m, n):
return math.comb(m + n - 2, m - 1)
# Test case
m, n = 3, 7
print("Unique Paths (Combinatorics):", uniquePaths(m, n)) # Output: 28
Complexity Analysis:
Dynamic Programming Approach:
- Time Complexity: O(m * n), where
mandnare the dimensions of the grid. We process each cell exactly once. - Space Complexity: O(n) for the optimized DP approach, where
nis the number of columns.
Combinatorics Approach:
- Time Complexity: O(min(m, n)), for calculating the binomial coefficient.
- Space Complexity: O(1), since we don’t need any additional space other than a few variables.
Conclusion:
The Dynamic Programming approach is a clear and intuitive way to solve the problem with O(m * n) time complexity, and space optimization can make it more efficient. Alternatively, the Combinatorics approach gives an elegant solution with O(min(m, n)) time complexity. Both approaches are suitable depending on the constraints.