Ways to Reach Origin Using Dynamic Programming

Problem Statement

Geek is standing at a point (x, y) on a 2D grid and wants to reach the origin (0, 0).

From any point, Geek can make only two types of moves:

Left: (x, y) → (x - 1, y)
Down: (x, y) → (x, y - 1)

The task is to find the total number of distinct paths from (x, y) to (0, 0).

Since the answer can be very large, return the answer modulo 10^9 + 7.

Understanding the Problem

At every point (x, y), Geek has at most two choices:

Move one step left.
Move one step down.

Every different sequence of these moves represents a different path.

For example, if Geek starts at (2, 1), three moves are required:

2 left moves
1 down move

The possible paths are:

Left → Left → Down
Left → Down → Left
Down → Left → Left

Therefore, there are 3 distinct paths.

The main challenge is to calculate this number efficiently when x and y become large.

What Is Dynamic Programming?

Dynamic Programming (DP) is a problem-solving technique used when a problem can be divided into smaller subproblems whose results can be reused.

Instead of solving the same smaller problem repeatedly, we calculate it once and store the result.

Dynamic Programming generally involves two important ideas:

State: Defines what a particular DP value represents.
Transition or Recurrence: Defines how one state can be calculated from previously solved states.

For this problem, we can use a 2D DP table to store the number of paths from every point to the origin.

Defining the DP State

Let:

dp[i][j]

represent the number of distinct paths from (i, j) to (0, 0).

This definition is important because it tells us exactly what every value in the DP table means.

For example:

dp[0][0] = 1

There is one way to be at the origin: we are already there.

Similarly:

dp[1][0] = 1

because the only possible path is:

(1, 0) → (0, 0)

And:

dp[0][2] = 1

because the only possible path is:

(0, 2) → (0, 1) → (0, 0)

Example

Input

x = 3
y = 6

Output

Explanation

To reach (0, 0) from (3, 6), Geek needs:

3 left moves
6 down moves

Therefore, the total number of moves is:

3 + 6 = 9

We need to choose which 3 of these 9 positions contain the left moves.

So the answer is:

C(9, 3) = 84

Hence, the total number of distinct paths is 84.

The dynamic programming approach calculates the same result without directly computing the combination.

Finding the Recurrence Relation

From any position (i, j), Geek has two possible moves:

(i, j) → (i - 1, j)
(i, j) → (i, j - 1)

Therefore, every path from (i, j) must first move to one of these two positions.

The paths through (i - 1, j) are counted by:

dp[i - 1][j]

The paths through (i, j - 1) are counted by:

dp[i][j - 1]

Since these represent the two possible first moves, we add them together.

Therefore, the recurrence relation is:

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

This is the central idea behind the solution.

Base Cases

A base case is a problem state whose answer is known directly and does not require further calculation.

There are two important base cases in this problem.

First Column

If y = 0, Geek can only move left.

For example:

(3, 0) → (2, 0) → (1, 0) → (0, 0)

There is only one path.

Therefore:

dp[i][0] = 1

First Row

If x = 0, Geek can only move down.

For example:

(0, 3) → (0, 2) → (0, 1) → (0, 0)

There is only one path.

Therefore:

dp[0][j] = 1

These base cases allow us to calculate all remaining cells.

Approach: Dynamic Programming

This problem can be solved efficiently using Dynamic Programming (DP).

We create a 2D array where each cell stores the number of paths from that position to the origin.

The process is:

Create the DP table.
Initialize the first row.
Initialize the first column.
Calculate every remaining cell using the recurrence relation.
Return dp[x][y].

The table is filled from smaller coordinates toward (x, y) so that the required previous values are already available.

Java 21 Implementation

class Solution {
    public int ways(int x, int y) {
        int MOD = 1000000007;

        int[][] dp = new int[x + 1][y + 1];

        // Base cases
        for (int i = 0; i <= x; i++) {
            dp[i][0] = 1;
        }

        for (int j = 0; j <= y; j++) {
            dp[0][j] = 1;
        }

        // Calculate number of ways
        for (int i = 1; i <= x; i++) {
            for (int j = 1; j <= y; j++) {
                dp[i][j] = (int) (
                    ((long) dp[i - 1][j] + dp[i][j - 1]) % MOD
                );
            }
        }

        return dp[x][y];
    }
}

Code Explanation

1. Create the DP Table

int[][] dp = new int[x + 1][y + 1];

We create a 2D array where:

dp[i][j]

stores the number of paths from (i, j) to (0, 0).

The size is x + 1 by y + 1 because the coordinates start from 0.

For example, if:

x = 3
y = 3

the table contains coordinates from 0 through 3 in both dimensions.

2. Initialize the First Column

for (int i = 0; i <= x; i++) {
    dp[i][0] = 1;
}

When y = 0, there is no possibility of moving down.

The only possible movement is left.

Therefore, there is exactly one path for every position in the first column.

3. Initialize the First Row

for (int j = 0; j <= y; j++) {
    dp[0][j] = 1;
}

When x = 0, there is no possibility of moving left.

The only possible movement is down.

Therefore, there is exactly one path for every position in the first row.

4. Fill the DP Table

for (int i = 1; i <= x; i++) {
    for (int j = 1; j <= y; j++) {
        dp[i][j] = (int) (
            ((long) dp[i - 1][j] + dp[i][j - 1]) % MOD
        );
    }
}

For every cell (i, j), there are two possible previous positions:

(i - 1, j)
(i, j - 1)

Therefore:

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

The value from the cell above represents paths that start by moving down, while the value from the left represents paths that start by moving left.

We use long while adding the values to avoid integer overflow before taking modulo.

Why Do We Take Modulo?

The number of possible paths grows very quickly as x and y increase.

For example:

dp[3][3] = 20
dp[10][10] = 184756

For larger grids, the number can become extremely large and exceed the range of Java's int or even long.

The problem therefore asks us to return the answer modulo:

10^9 + 7

which is:

1000000007

The modulo operation keeps the stored values within a manageable range while preserving the required result.

DP Table Example

For:

x = 3
y = 3

the DP table becomes:

1  1  1  1
1  2  3  4
1  3  6  10
1  4  10 20

Let's calculate a few cells.

For (1, 1):

dp[1][1] = dp[0][1] + dp[1][0]
         = 1 + 1
         = 2

For (2, 2):

dp[2][2] = dp[1][2] + dp[2][1]
         = 3 + 3
         = 6

For (3, 3):

dp[3][3] = dp[2][3] + dp[3][2]
         = 10 + 10
         = 20

Therefore:

dp[3][3] = 20

So there are 20 different paths from (3, 3) to (0, 0).

Why Dynamic Programming Works

This problem has overlapping subproblems.

An overlapping subproblem occurs when the same smaller problem is needed multiple times while solving a larger problem.

For example, calculating the number of paths for different cells repeatedly requires values such as:

dp[i - 1][j]
dp[i][j - 1]

Instead of calculating these values repeatedly, Dynamic Programming stores them in the table.

The problem also has optimal substructure, because the solution for a larger state can be constructed from solutions to smaller states.

In this case:

Number of paths to (i, j)
        ↓
Paths through (i - 1, j)
+
Paths through (i, j - 1)

This makes Dynamic Programming a natural approach for the problem.

Alternative Mathematical Interpretation

There is also a combinatorial way to understand the result.

To move from (x, y) to (0, 0), Geek must make exactly:

x + y

moves.

Among those moves:

x moves are left moves.
y moves are down moves.

Therefore, the number of possible arrangements is:

C(x + y, x)

or equivalently:

C(x + y, y)

For example:

x = 3
y = 6

gives:

C(9, 3) = 84

The DP solution reaches the same result through the recurrence:

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

The DP approach is especially useful when explaining the problem in terms of grid traversal and when extending the problem with obstacles or additional constraints.

Complexity Analysis

There are (x + 1) × (y + 1) cells in the DP table.

For each cell, we perform constant-time work.

Time Complexity

O(x × y)

Auxiliary Space

O(x × y)

The space can be optimized further to O(y) by using a one-dimensional DP array, but the 2D implementation is easier to understand because each state directly represents a grid position.

Key Takeaway

The important recurrence for this problem is:

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

with the base cases:

dp[i][0] = 1
dp[0][j] = 1

The key idea is that every path from (i, j) must begin with either a left move or a down move. Therefore, the number of paths can be obtained by adding the paths from those two neighboring positions.

This is a classic 2D Grid Dynamic Programming problem and is also closely related to the combinatorial formula:

C(x + y, x)

Understanding the DP state, recurrence relation, and base cases makes this pattern useful for many other grid problems, including problems involving obstacles, restricted cells, and different movement rules.

Problem Statement

Geek is standing at a point (x, y) on a 2D grid and wants to reach the origin (0, 0).

From any point, Geek can make only two types of moves:

Left: (x, y) → (x - 1, y)
Down: (x, y) → (x, y - 1)

The task is to find the total number of distinct paths from (x, y) to (0, 0).

Since the answer can be very large, return the answer modulo 10^9 + 7.

Understanding the Problem

At every point (x, y), Geek has at most two choices:

Move one step left.
Move one step down.

Every different sequence of these moves represents a different path.

For example, if Geek starts at (2, 1), three moves are required:

2 left moves
1 down move

The possible paths are:

Left → Left → Down
Left → Down → Left
Down → Left → Left

Therefore, there are 3 distinct paths.

The main challenge is to calculate this number efficiently when x and y become large.

What Is Dynamic Programming?

Dynamic Programming (DP) is a problem-solving technique used when a problem can be divided into smaller subproblems whose results can be reused.

Instead of solving the same smaller problem repeatedly, we calculate it once and store the result.

Dynamic Programming generally involves two important ideas:

State: Defines what a particular DP value represents.
Transition or Recurrence: Defines how one state can be calculated from previously solved states.

For this problem, we can use a 2D DP table to store the number of paths from every point to the origin.

Defining the DP State

Let:

dp[i][j]

represent the number of distinct paths from (i, j) to (0, 0).

This definition is important because it tells us exactly what every value in the DP table means.

For example:

dp[0][0] = 1

There is one way to be at the origin: we are already there.

Similarly:

dp[1][0] = 1

because the only possible path is:

(1, 0) → (0, 0)

And:

dp[0][2] = 1

because the only possible path is:

(0, 2) → (0, 1) → (0, 0)

Example

Input

x = 3
y = 6

Output

Explanation

To reach (0, 0) from (3, 6), Geek needs:

3 left moves
6 down moves

Therefore, the total number of moves is:

3 + 6 = 9

We need to choose which 3 of these 9 positions contain the left moves.

So the answer is:

C(9, 3) = 84

Hence, the total number of distinct paths is 84.

The dynamic programming approach calculates the same result without directly computing the combination.

Finding the Recurrence Relation

From any position (i, j), Geek has two possible moves:

(i, j) → (i - 1, j)
(i, j) → (i, j - 1)

Therefore, every path from (i, j) must first move to one of these two positions.

The paths through (i - 1, j) are counted by:

dp[i - 1][j]

The paths through (i, j - 1) are counted by:

dp[i][j - 1]

Since these represent the two possible first moves, we add them together.

Therefore, the recurrence relation is:

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

This is the central idea behind the solution.

Base Cases

A base case is a problem state whose answer is known directly and does not require further calculation.

There are two important base cases in this problem.

First Column

If y = 0, Geek can only move left.

For example:

(3, 0) → (2, 0) → (1, 0) → (0, 0)

There is only one path.

Therefore:

dp[i][0] = 1

First Row

If x = 0, Geek can only move down.

For example:

(0, 3) → (0, 2) → (0, 1) → (0, 0)

There is only one path.

Therefore:

dp[0][j] = 1

These base cases allow us to calculate all remaining cells.

Approach: Dynamic Programming

This problem can be solved efficiently using Dynamic Programming (DP).

We create a 2D array where each cell stores the number of paths from that position to the origin.

The process is:

Create the DP table.
Initialize the first row.
Initialize the first column.
Calculate every remaining cell using the recurrence relation.
Return dp[x][y].

The table is filled from smaller coordinates toward (x, y) so that the required previous values are already available.

Java 21 Implementation

class Solution {
    public int ways(int x, int y) {
        int MOD = 1000000007;

        int[][] dp = new int[x + 1][y + 1];

        // Base cases
        for (int i = 0; i <= x; i++) {
            dp[i][0] = 1;
        }

        for (int j = 0; j <= y; j++) {
            dp[0][j] = 1;
        }

        // Calculate number of ways
        for (int i = 1; i <= x; i++) {
            for (int j = 1; j <= y; j++) {
                dp[i][j] = (int) (
                    ((long) dp[i - 1][j] + dp[i][j - 1]) % MOD
                );
            }
        }

        return dp[x][y];
    }
}

Code Explanation

1. Create the DP Table

int[][] dp = new int[x + 1][y + 1];

We create a 2D array where:

dp[i][j]

stores the number of paths from (i, j) to (0, 0).

The size is x + 1 by y + 1 because the coordinates start from 0.

For example, if:

x = 3
y = 3

the table contains coordinates from 0 through 3 in both dimensions.

2. Initialize the First Column

for (int i = 0; i <= x; i++) {
    dp[i][0] = 1;
}

When y = 0, there is no possibility of moving down.

The only possible movement is left.

Therefore, there is exactly one path for every position in the first column.

3. Initialize the First Row

for (int j = 0; j <= y; j++) {
    dp[0][j] = 1;
}

When x = 0, there is no possibility of moving left.

The only possible movement is down.

Therefore, there is exactly one path for every position in the first row.

4. Fill the DP Table

for (int i = 1; i <= x; i++) {
    for (int j = 1; j <= y; j++) {
        dp[i][j] = (int) (
            ((long) dp[i - 1][j] + dp[i][j - 1]) % MOD
        );
    }
}

For every cell (i, j), there are two possible previous positions:

(i - 1, j)
(i, j - 1)

Therefore:

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

The value from the cell above represents paths that start by moving down, while the value from the left represents paths that start by moving left.

We use long while adding the values to avoid integer overflow before taking modulo.

Why Do We Take Modulo?

The number of possible paths grows very quickly as x and y increase.

For example:

dp[3][3] = 20
dp[10][10] = 184756

For larger grids, the number can become extremely large and exceed the range of Java's int or even long.

The problem therefore asks us to return the answer modulo:

10^9 + 7

which is:

1000000007

The modulo operation keeps the stored values within a manageable range while preserving the required result.

DP Table Example

For:

x = 3
y = 3

the DP table becomes:

1  1  1  1
1  2  3  4
1  3  6  10
1  4  10 20

Let's calculate a few cells.

For (1, 1):

dp[1][1] = dp[0][1] + dp[1][0]
         = 1 + 1
         = 2

For (2, 2):

dp[2][2] = dp[1][2] + dp[2][1]
         = 3 + 3
         = 6

For (3, 3):

dp[3][3] = dp[2][3] + dp[3][2]
         = 10 + 10
         = 20

Therefore:

dp[3][3] = 20

So there are 20 different paths from (3, 3) to (0, 0).

Why Dynamic Programming Works

This problem has overlapping subproblems.

An overlapping subproblem occurs when the same smaller problem is needed multiple times while solving a larger problem.

For example, calculating the number of paths for different cells repeatedly requires values such as:

dp[i - 1][j]
dp[i][j - 1]

Instead of calculating these values repeatedly, Dynamic Programming stores them in the table.

The problem also has optimal substructure, because the solution for a larger state can be constructed from solutions to smaller states.

In this case:

Number of paths to (i, j)
        ↓
Paths through (i - 1, j)
+
Paths through (i, j - 1)

This makes Dynamic Programming a natural approach for the problem.

Alternative Mathematical Interpretation

There is also a combinatorial way to understand the result.

To move from (x, y) to (0, 0), Geek must make exactly:

x + y

moves.

Among those moves:

x moves are left moves.
y moves are down moves.

Therefore, the number of possible arrangements is:

C(x + y, x)

or equivalently:

C(x + y, y)

For example:

x = 3
y = 6

gives:

C(9, 3) = 84

The DP solution reaches the same result through the recurrence:

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

The DP approach is especially useful when explaining the problem in terms of grid traversal and when extending the problem with obstacles or additional constraints.

Complexity Analysis

There are (x + 1) × (y + 1) cells in the DP table.

For each cell, we perform constant-time work.

Time Complexity

O(x × y)

Auxiliary Space

O(x × y)

The space can be optimized further to O(y) by using a one-dimensional DP array, but the 2D implementation is easier to understand because each state directly represents a grid position.

Key Takeaway

The important recurrence for this problem is:

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

with the base cases:

dp[i][0] = 1
dp[0][j] = 1

This is a classic 2D Grid Dynamic Programming problem and is also closely related to the combinatorial formula:

C(x + y, x)