Each cell can only be reached from directly above or directly to its left, so dp[i][j] = dp[i-1][j] + dp[i][j-1].

Unique Paths

medium

Acceptance: 55%

Dynamic Programming

A traveler starts in the upper-left cell of an m-by-n grid and wants to reach the lower-right cell. Movement is restricted to going one cell right or one cell down at each step. Count how many distinct routes exist from start to finish.

Examples

Example 1:

Input:m = 4, n = 3

Output:10

Explanation: There are 10 distinct routes from the top-left to the bottom-right of a 4x3 grid.

Example 2:

Input:m = 2, n = 5

Output:5

Explanation: In a 2x5 grid, there are 5 distinct routes.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Unique Paths

Examples

Hints

Related Problems