[Dynamic Programming] Unique Paths in a Grid - Easy

The Unique Paths problem is a well-known challenge in dynamic programming. It asks us to find how many different paths we can take to go from the top-left corner to the bottom-right corner of a grid. We can only move to the right or down.

We can use dynamic programming methods to solve this. These methods help us find the number of ways to reach each cell in the grid. We base this on values we have already calculated. This approach is much better than using a simple recursive way.

In this article, we will talk about the Unique Paths problem in detail. We will look at different solutions, including dynamic programming methods in Java, Python, and C++. We will also look at solutions that use less space and a recursive method with memoization. By the end, we will understand the Unique Paths problem and how to solve it. The sections we will cover are:

  • [Dynamic Programming] Unique Paths in a Grid - Easy Solutions Overview
  • Understanding the Unique Paths Problem
  • Dynamic Programming Approach to Unique Paths in Java
  • Dynamic Programming Approach to Unique Paths in Python
  • Dynamic Programming Approach to Unique Paths in C++
  • Optimized Space Complexity Solution in Java
  • Optimized Space Complexity Solution in Python
  • Optimized Space Complexity Solution in C++
  • Recursive Approach to Unique Paths with Memoization
  • Frequently Asked Questions

If we want to learn more about dynamic programming ideas, we can read articles on similar topics. For example, we can check out Dynamic Programming Fibonacci Number and Dynamic Programming Climbing Stairs for more insights.

Understanding the Unique Paths Problem

The Unique Paths problem is a well-known challenge in dynamic programming. It asks us how many different ways we can move through a grid. We start from the top-left corner and go to the bottom-right corner. We can only move down or right. Given an m x n grid, our goal is to find out how many unique paths lead to the destination cell.

Problem Definition

  • We start at position (0, 0) and need to reach position (m-1, n-1).
  • We can only move down or right.
  • The grid size is m rows and n columns.

Example

For a grid of size 3 x 2:

1 2
3 4
5 6

The unique paths from the top-left to the bottom-right are: 1. Down -> Down -> Right 2. Down -> Right -> Down 3. Right -> Down -> Down 4. Right -> Right -> Down

So, the total number of unique paths is 3.

Mathematical Insight

We can also find the number of unique paths using math. The total moves we need to reach the destination is (m - 1) + (n - 1). We can think of this problem as choosing m - 1 down moves from a total of m + n - 2 moves. We can write this as: [ C(m+n-2, m-1) = ]

Key Points

  • We can solve the problem using different methods. These include recursive, dynamic programming, and combinatorial.
  • The dynamic programming method builds a solution step-by-step. It stores results of smaller problems in a 2D array or even in a 1D array to save space.
  • We can also make the solution better to use less space while keeping the time it takes the same at (O(m n)).

This problem is important for learning dynamic programming. It connects to other problems like Climbing Stairs and similar ones.

Dynamic Programming Approach to Unique Paths in Java

We can solve the Unique Paths problem using dynamic programming in Java. We will create a 2D array dp. In this array, dp[i][j] shows the number of unique paths to get to the cell (i, j) in an m x n grid. We can reach a cell from the cell above it (i-1, j) or from the cell to the left (i, j-1).

Here is the simple approach step by step:

  1. Initialization: We set dp[0][j] = 1 for all j in the first row. We also set dp[i][0] = 1 for all i in the first column. There is only one way to reach any cell in the first row or column.

  2. Filling the DP Array: For each cell (i, j), the number of unique paths is the sum of the unique paths from the cell above and the cell to the left:

    dp[i][j] = dp[i-1][j] + dp[i][j-1];

  3. Return the Result: The value at dp[m-1][n-1] tells us the total unique paths from the top-left to the bottom-right of the grid.

Java Code Implementation

public class UniquePaths {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // Initialize the first row and first column
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1; // Only one way to reach any cell in the first column
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1; // Only one way to reach any cell in the first row
        }

        // Fill the dp array
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1]; // Return the number of unique paths to the bottom-right corner
    }

    public static void main(String[] args) {
        UniquePaths up = new UniquePaths();
        System.out.println("Unique Paths: " + up.uniquePaths(3, 7)); // Example usage
    }
}

This code helps us find the number of unique paths in an m x n grid by using dynamic programming. For more advanced problems in dynamic programming, we can look at related articles like Dynamic Programming Fibonacci Number and Dynamic Programming Climbing Stairs.

Dynamic Programming Approach to Unique Paths in Python

The Unique Paths problem is about finding how many ways we can reach the bottom-right corner of a grid. We start from the top-left corner and can only move down or right. We can solve this problem well using dynamic programming.

Dynamic Programming Implementation

In our dynamic programming approach, we use a 2D array called dp. Here, dp[i][j] shows the number of unique paths to reach the cell (i, j). We can find this value by looking at the cells above and to the left:

  • Base Case: The first row and the first column can only be reached in one way. We can either move all the way right or all the way down.

  • Recurrence Relation:

    dp[i][j] = dp[i-1][j] + dp[i][j-1]

Here is a simple implementation in Python:

def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

# Example Usage
print(uniquePaths(3, 7))  # Output: 28

Explanation of the Code

  • We start by making a 2D list dp with size m x n, and we fill it with 1s.
  • We go through the grid starting from (1, 1) to fill in the number of unique paths for each cell.
  • At the end, we return the value at dp[m-1][n-1]. This value shows the total unique paths from the top-left to the bottom-right corner.

This method has a time complexity of O(mn) and a space complexity of O(mn).

For more dynamic programming challenges and solutions, we can check out these articles: - Dynamic Programming Fibonacci Number - Easy - Dynamic Programming Climbing Stairs - Easy - Dynamic Programming Minimum Cost Climbing Stairs - Easy

Dynamic Programming Approach to Unique Paths in C++

We can solve the Unique Paths problem using the Dynamic Programming method in C++. This method builds a 2D DP table. This table helps us keep track of how many ways we can reach each cell in a grid. The grid has size m x n. Here, m is the number of rows and n is the number of columns. Our goal is to find how many unique paths there are from the top-left corner (0,0) to the bottom-right corner (m-1,n-1). We can only move to the right or down.

Algorithm

  1. Initialize a DP Table: We create a 2D vector dp of size m x n. The value dp[i][j] shows the number of unique paths to reach cell (i, j).
  2. Base Case: We set dp[0][0] = 1. There is one way to reach the starting cell.
  3. Fill the DP Table: We go through each cell. For each cell, the number of ways to reach it is the sum of the number of ways to reach the cell above it and the cell to the left:
    • dp[i][j] = dp[i-1][j] + dp[i][j-1] (if i > 0 and j > 0).
  4. Return the Result: The value at dp[m-1][n-1] gives the total unique paths to the bottom-right corner.

C++ Code Implementation

#include <vector>
using namespace std;

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // Initialize the first row and first column
        for (int i = 0; i < m; ++i) {
            dp[i][0] = 1; // Only one way to reach any cell in the first column
        }
        for (int j = 0; j < n; ++j) {
            dp[0][j] = 1; // Only one way to reach any cell in the first row
        }
        
        // Fill the DP table
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
        return dp[m - 1][n - 1];
    }
};

Complexity Analysis

  • Time Complexity: O(m * n). We go through each cell in the grid one time.
  • Space Complexity: O(m * n). We need a 2D array to keep the number of paths.

This Dynamic Programming approach helps us find the number of unique paths in a grid. It works well even for larger grid sizes. If we want to learn more about dynamic programming, we can check related problems like Dynamic Programming - Fibonacci Number or Dynamic Programming - Climbing Stairs.

Optimized Space Complexity Solution in Java

We can solve the Unique Paths problem in Java with a better space usage. This solution cuts the space from O(m * n) to O(n) by using a 1D array. We do not need a 2D array to keep track of paths. Instead, we only use one row to hold the results for the current and previous rows.

Implementation

We will go through each cell of the grid. We update our array based on the paths from the top and left cells. Here is the code:

public class UniquePaths {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        dp[0] = 1; // Starting point
        
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1]; // Update current cell based on the top and left cells
            }
        }
        
        return dp[n - 1]; // The number of unique paths to the bottom-right corner
    }

    public static void main(String[] args) {
        UniquePaths up = new UniquePaths();
        int result = up.uniquePaths(3, 7); // Example for a 3x7 grid
        System.out.println("Unique Paths: " + result);
    }
}

Explanation

  • Initialization: We start with an array dp that has size n (the number of columns). The first element is 1, which shows the starting position.
  • Nested Loop: The outer loop goes through each row. The inner loop updates the dp array.
  • Update Rule: We update each cell at dp[j] by adding the value from the left cell (dp[j - 1]).
  • Result: The last element of the dp array gives the total number of unique paths to reach the bottom-right corner.

This method cuts down the space we use, while the time complexity stays at O(m * n). For more insights into dynamic programming, check out articles about Fibonacci Number and Climbing Stairs.

Optimized Space Complexity Solution in Python

To solve the Unique Paths problem in Python with better space use, we can keep track of only the current and previous row. We know that to find the number of unique paths to a cell, we only need the values from the current row and the row above.

Code Implementation

Here is the Python code for the optimized space complexity solution:

def uniquePaths(m: int, n: int) -> int:
    # Create a 1D array to store the number of ways to reach each cell in the current row
    dp = [1] * n
    
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]  # Update the current cell using values from the previous row
    
    return dp[-1]  # The last cell contains the total unique paths to reach the bottom-right corner

# Example usage
print(uniquePaths(3, 7))  # Output: 28

Explanation

  • Initialization: We start with a list dp that has size n (the number of columns). All values in this list are 1. This shows the number of unique paths to each cell in the first row.
  • Row Iteration: For each next row, we go through each cell starting from the second column.
  • Path Calculation: We update each cell’s value. We add the value from the cell on its left (from the current row) and the value from the cell above it (from the previous row). This counts the unique paths to that cell.
  • Space Complexity: This method cuts down the space needed from O(m * n) to O(n). We only keep one row of results at a time.

This way is good and keeps the performance high for solving the Unique Paths problem in a grid. It also saves a lot of memory compared to using a full 2D array.

Optimized Space Complexity Solution in C++

To solve the Unique Paths problem with better space usage in C++, we use a single array. This array helps us track how many unique paths go to each cell in the grid. Instead of using a full 2D array, we update our array in-place. This change reduces the space needed from O(m*n) to O(n).

C++ Code Implementation

#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    vector<int> dp(n, 1); // We create a 1D array of size n, filled with 1

    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[j] += dp[j - 1]; // We update the current cell with paths from top and left
        }
    }
    return dp[n - 1]; // The last element gives the number of unique paths
}

Explanation

  • Initialization: We start by making a 1D vector called dp that has size n. All elements are set to 1. This shows the number of ways to reach each cell in the first row. There is only one way to reach any cell in that row.
  • Dynamic Programming Update: For each row after the first, we go through the columns and update the dp array. The value at dp[j] is updated to be the sum of paths from the cell above (dp[j]) and the cell to the left (dp[j - 1]).
  • Final Output: After we finish all rows, dp[n - 1] has the total number of unique paths from the top-left to the bottom-right of the grid.

This way is smart and uses less space. It is good for bigger grids. If we want to learn more about dynamic programming, we can check out the Dynamic Programming - Climbing Stairs article.

Recursive Approach to Unique Paths with Memoization

We can solve the unique paths problem using a recursive method with memoization. This helps us to avoid recalculating results for problems we already solved. So, it makes our solution much faster.

Problem Definition

We have a grid of size m x n. From the top-left corner (0, 0), we can only move down or to the right. Our goal is to find how many unique paths we have to reach the bottom-right corner (m-1, n-1).

Recursive Function with Memoization

The recursive function checks where we are and adds the unique paths from the cell below and the cell to the right. We use memoization to store results we have already calculated in a cache.

Java Implementation

import java.util.HashMap;

public class UniquePaths {
    public int uniquePaths(int m, int n) {
        return countPaths(m - 1, n - 1, new HashMap<>());
    }

    private int countPaths(int row, int col, HashMap<String, Integer> memo) {
        if (row < 0 || col < 0) return 0;
        if (row == 0 && col == 0) return 1;

        String key = row + "," + col;
        if (memo.containsKey(key)) return memo.get(key);

        int paths = countPaths(row - 1, col, memo) + countPaths(row, col - 1, memo);
        memo.put(key, paths);
        return paths;
    }
}

Python Implementation

def unique_paths(m: int, n: int) -> int:
    memo = {}
    return count_paths(m - 1, n - 1, memo)

def count_paths(row: int, col: int, memo: dict) -> int:
    if row < 0 or col < 0:
        return 0
    if row == 0 and col == 0:
        return 1

    key = (row, col)
    if key in memo:
        return memo[key]

    memo[key] = count_paths(row - 1, col, memo) + count_paths(row, col - 1, memo)
    return memo[key]

C++ Implementation

#include <unordered_map>
#include <string>

class Solution {
public:
    int uniquePaths(int m, int n) {
        std::unordered_map<std::string, int> memo;
        return countPaths(m - 1, n - 1, memo);
    }

private:
    int countPaths(int row, int col, std::unordered_map<std::string, int>& memo) {
        if (row < 0 || col < 0) return 0;
        if (row == 0 && col == 0) return 1;

        std::string key = std::to_string(row) + "," + std::to_string(col);
        if (memo.find(key) != memo.end()) return memo[key];

        memo[key] = countPaths(row - 1, col, memo) + countPaths(row, col - 1, memo);
        return memo[key];
    }
};

Explanation of Code

  • Base Case: When we reach the position (0, 0), we have one unique path. If we go out of bounds, we return 0.
  • Memoization: We use a hashmap or dictionary to keep the results of paths we computed before for specific grid points.
  • Recursive Calls: The function calls itself for the cell below and the cell to the right, and we add the results.

This method cuts down the time it takes compared to a simple recursive solution. It makes it possible to work with bigger grids. For more details about dynamic programming, we can check other articles like Dynamic Programming Fibonacci Number or Dynamic Programming Climbing Stairs.

Frequently Asked Questions

1. What is the Unique Paths problem in dynamic programming?

The Unique Paths problem is a well-known challenge in dynamic programming. The goal is to count how many different ways we can get to the bottom-right corner of a grid from the top-left corner. We can only move down or right. We can solve this problem well using dynamic programming. This helps us see how we can use recursive relationships and changes in state for problems that use grids.

2. How can I solve Unique Paths using dynamic programming in Java?

To solve the Unique Paths problem in Java, we can make a 2D array. This array will keep track of how many ways we can reach each cell. We will start by setting the first row and the first column to 1. This is because there is only one way to reach those cells. Next, we fill in the rest of the array. We do this by adding the paths from the cell above and the cell to the left. For more details, look at our section on the Dynamic Programming Approach to Unique Paths in Java.

3. Is there an optimized space complexity solution for Unique Paths in Python?

Yes, we can find a better space solution for the Unique Paths problem in Python. Instead of using a 2D array, we can use a 1D array. By keeping track of only the current and previous rows, we can lower the space needed from O(m*n) to O(n). This method uses the connection between the current position and the ones before it. For more information, check our section on the Optimized Space Complexity Solution in Python.

4. Can I implement the Unique Paths algorithm using recursion and memoization?

Yes, we can also solve the Unique Paths problem with a recursive method and memoization to make it faster. This way, we explore all possible paths to the bottom-right corner. We store the results of smaller problems so we do not repeat calculations. For a complete explanation, see our section on the Recursive Approach to Unique Paths with Memoization.

5. How does the Unique Paths problem relate to other dynamic programming problems?

The Unique Paths problem is similar to other dynamic programming problems. For example, it is like the Fibonacci sequence or the Climbing Stairs problem. Knowing these connections helps us understand dynamic programming better. For example, in the Climbing Stairs problem, we can take one or two steps at a time. For more on related topics, see our article on Dynamic Programming: Climbing Stairs.