Grid Lattice Paths with Memoization

core

Implement long long paths(int n, int m), the number of monotonic lattice paths from corner (0, 0) to corner (n, m) of an n by m grid, moving only right or down one step at a time. Use the recursion f(i, j) = f(i - 1, j) + f(i, j - 1) with base case f(i, 0) = f(0, j) = 1, and back it with a memo table: declare a table of size (n + 1) by (m + 1), and check the table for an already-computed entry before recursing further. Both n and m are at most 18, and the true answer always fits in a 64-bit integer (long long in C++; Python ints are arbitrary precision; JavaScript numbers are exact integers up to 2^53, and the largest answer here is C(36, 18) ≈ 9.1e9, well inside that).

Example: paths(2, 2) returns 6. Building up: f(1,1) = f(0,1) + f(1,0) = 1 + 1 = 2; f(1,2) = f(0,2) + f(1,1) = 1 + 2 = 3; f(2,1) = f(1,1) + f(2,0) = 2 + 1 = 3; f(2,2) = f(1,2) + f(2,1) = 3 + 3 = 6.

Input format: each test in tests/*.in is laid out as:

Line 1: n m, the two arguments to paths(n, m).

Test 01.in reads:

0 0

This is the degenerate 0 x 0 grid.

Where you'll use it:

✦ Solution & editorial unlock with the pass.