Challenge: Paths in a Grid

Lab C++ Intermediate 20 points

A robot starts at the top-left of an r × c grid and can only move right or down. Print the number of paths to the bottom-right corner, using recursion with memoization.

Input

Two whole numbers r c (1 ≤ r, c ≤ 16).

Output

The number of paths.

Example

Input

2 2

Output

Sample input available Sample output available

Editor

C++

Hints

One row or one column: exactly 1 path.

paths(r, c) = paths(r - 1, c) + paths(r, c - 1).

Store answers in a 2D array.

Solution explanation

Each (r, c) is solved once: O(r × c).

Show solution

#include <iostream>
using namespace std;

long long memo[17][17];

long long paths(int r, int c) {
    if (r == 1 || c == 1) return 1;
    if (memo[r][c]) return memo[r][c];
    return memo[r][c] = paths(r - 1, c) + paths(r, c - 1);
}

int main() {
    int r, c;
    cin >> r >> c;
    cout << paths(r, c) << endl;
    return 0;
}

Output

Answer