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
- 1 ≤ m, n ≤ 1000
Example 1
Input
3 7
Output
28
Example 2
Input
3 2
Output
3
Hints
- You reach cell (i, j) either from the cell above or from the cell on the left.
- 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]);
}
}