Unique Paths in Grid in Java: Explanation & Practice

Problem summary

Given an m×n grid, count unique paths from top-left to bottom-right. You can only move right or down.

Starter code

public class Main {
    public static void main(String[] args) {
        int m = 3, n = 7;
        
        // dp[i][j] = paths to reach cell (i,j)
        // dp[i][j] = dp[i-1][j] + dp[i][j-1]
        // Print: Paths: 28
    }
}

Expected output and test cases

• 3x7 grid

  Paths: 28

• 2x3 grid

  Paths: 3

• 1x1 grid

  Paths: 1

Hints

1. First row and first column have only 1 path each
2. For other cells: you came from above or from left
3. dp[i][j] = dp[i-1][j] + dp[i][j-1]
4. Can optimize to 1D array since we only need previous row

Related Data Structures & Algorithms exercises

• Practice Longest Increasing Subsequence in Java
• Practice 0/1 Knapsack in Java
• Practice Longest Common Subsequence in Java

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler