Dynamic Programming - Memoization Example using the GridTraveler problem

gridTraveler.cpp

#include <iostream>
#include <unordered_map>
#include <vector>

/* --------------------------------------------------------------------------------------- */
/*	GridTraveler Problem
	You are a traveler on a 2D grid. You begin in the top-left corner and your goal
	is to travel to the bottom-right corner. You may only move down or right.
	In how many ways can you travel to the goal on a grid with dimension m X n?
	Write a function gridTraveler(m,n) that calculates this.

	Example 2 X 4 Grid:
	The arrows show just one path through the grid.
	In total, there are 4 possible paths through the grid: RRRD, RRDR, RDRR, DRRR
	 _______________________________
	|       |       |       |       |
	| start ----    |       |       |
	|_______|___|___|_______|_______|
	|       |   |   |       |       |
	|       |    ------------> end  |
	|_______|_______|_______|_______|
	
	The following code explores two solutions to this problem and compares their runtimes.
	1. The brute force recursive strategy
	2. Recursion, but with memoization of previous calulations
	
*/ 
/* --------------------------------------------------------------------------------------- */

// helper function that creates a hash code for an std::pair
struct pair_hash
{
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};

// recursive gridTraveler
// O(2^(m+n)) time, O(m+n) space
unsigned long long gridTraveler_recursive(int m, int n)
{
	if ((m <= 0) || (n <= 0)) return 0;
	if ((m == 1) || (n == 1)) return 1;
	return gridTraveler_recursive(m-1, n) + gridTraveler_recursive(m, n-1);
}

// memoization gridTraveler
// O(m*n) time, O(m+n) space
unsigned long long gridTraveler(int m, int n)
{
	// Pseudocode:
	// if n in memo, return memo(n)
	// do recursive implementation, but save results in memo
	
	using GridDim = std::pair<int,int>;
	using GridMemo = std::unordered_map< GridDim, unsigned long long, pair_hash>;
	static GridMemo memo;

	// find the pair or reverse pair in the memo
	GridDim pair = std::make_pair(m, n);
	GridDim reverse_pair = std::make_pair(n, m);
	GridMemo::const_iterator it = memo.find(pair);
	if ( it == memo.end() ) it = memo.find(reverse_pair);
	
	// if the current GridDim has already been calculated, return it
	if ( it != memo.end() ) return it->second;
	
	// otherwise, do recursive method, but save memo
	if ((m <= 0) || (n <= 0)) return 0;
	if ((m == 1) || (n == 1)) return 1;
	memo.insert(std::make_pair(pair, gridTraveler(m-1, n) + gridTraveler(m, n-1)));
	return memo[pair];
}


int main()
{
	// test both GridTraveler implementations
	std::vector<std::pair<int,int>> testGrids{{0,1},{27,-1},{1,1},{2,2},{2,3},{5,5},{12,13},{18,18}};
	
	std::cout << "Running Memoized Implementation (time complexity = O(M*N)):" << std::endl;
	for (std::pair<int,int> grid : testGrids)
	{
		std::cout << gridTraveler(grid.first,grid.second) << std::endl;
	}
	
	std::cout << "Running Brute Force Implementation (time complexity = O(2^(M*N))):" << std::endl;
	for (std::pair<int,int> grid : testGrids)
	{
		std::cout << gridTraveler_recursive(grid.first,grid.second) << std::endl;
	}
	
	return 0;
}