Unique Paths - Java Solution

1. Introduction

This blog post explores a classic problem in combinatorics and dynamic programming - counting the number of unique paths a robot can take in a grid. The robot can only move either down or right at any point, starting from the top-left corner of an m x n grid and aiming to reach the bottom-right corner. This problem is a good example of how to approach path-finding problems in a grid setting.

Problem

Given two integers m and n representing the dimensions of an m x n grid, the task is to determine the number of unique paths that a robot, starting at the top-left corner, can take to reach the bottom-right corner. The robot can only move either down or right at any point in time.

2. Solution Steps

1. Use dynamic programming to solve the problem.

2. Create a 2D array dp where dp[i][j] represents the number of ways to reach cell (i, j).

3. Initialize the first row and first column of dp as 1, since there's only one way to reach cells in the first row or column.

4. Fill the rest of dp using the relation: dp[i][j] = dp[i - 1][j] + dp[i][j - 1].

5. Return the value of dp[m - 1][n - 1], which represents the number of unique paths to the bottom-right corner.

3. Code Program

public class UniquePaths {
    public static void main(String[] args) {
        int m = 3, n = 7;
        System.out.println(uniquePaths(m, n)); // Test the function
    }

    // Function to count the number of unique paths
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // Initialize the first row and column
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        // 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];
    }
}

Output:

28

Explanation:

1. uniquePaths: This function calculates the number of unique paths on an m x n grid. It uses a dynamic programming approach, where dp[i][j] represents the number of paths to reach cell (i, j).

2. The first row and column are initialized to 1, as there is only one way to reach these cells - either by moving right (for the first row) or down (for the first column).

3. The function then iteratively fills the dp array based on the fact that the number of paths to a cell is the sum of paths to its top and left cells.

4. The bottom-right corner of the dp array, dp[m - 1][n - 1], holds the total number of unique paths from the top-left corner to the bottom-right corner.

5. The approach ensures an efficient calculation of the number of paths, avoiding any redundant computations.