Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Unique Grid Paths

Easy · Dynamic Programming · Asked at Amazon, Google, Microsoft, TCS, Infosys

A robot starts at the top-left of an m × n grid and can only move right or down. Count the paths to the bottom-right corner, modulo 10^9 + 7.

Input

One line: m n.

Output

The number of paths modulo 1000000007.

Constraints

Example 1

Input

3 7

Output

28

Example 2

Input

3 2

Output

3

Hints

  1. You reach cell (i, j) either from the cell above or from the cell on the left.
  2. paths[i][j] = paths[i−1][j] + paths[i][j−1] (mod 10^9 + 7). The first row and column have exactly 1 path each. One row of memory is enough.

Approach

Keep a single row dp of length n filled with 1, which is the first row. For each later row, update left to right with dp[j] = (dp[j] + dp[j − 1]) % MOD. Before the update, dp[j] holds the cell above; dp[j − 1] already holds the cell to the left in the current row. Taking the modulo at every step keeps numbers small. (The closed form is C(m + n − 2, m − 1), but it needs modular inverses.)

Complexity: O(m·n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    const long long MOD = 1000000007;
    int m, n;
    cin >> m >> n;
    vector<long long> dp(n, 1);
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++) dp[j] = (dp[j] + dp[j - 1]) % MOD;
    cout << dp[n - 1] << "\n";
    return 0;
}

Python solution

MOD = 10**9 + 7
m, n = map(int, input().split())
dp = [1] * n
for _ in range(1, m):
    for j in range(1, n):
        dp[j] = (dp[j] + dp[j - 1]) % MOD
print(dp[-1])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        final long MOD = 1000000007;
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt();
        long[] dp = new long[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++) dp[j] = (dp[j] + dp[j - 1]) % MOD;
        System.out.println(dp[n - 1]);
    }
}

Solve Unique Grid Paths online · All practice problems