2D grid travel (Dynamic Programming) - recursive solution working but not memoized one

Question

Problem Statement - there's a 2D grid of dimensions m x n ,you are at the top left corner, find in how many ways you can reach the bottom right when you can only move down or right.

The code uses unordered map where the keys are strings like so "2,3" , "1,2" (the nodes in the tree) and their values are integers (no.of ways to reach that node).

The following is it's code which gives correct output for the recursive function gridTraveller(2,3); the output is 3. But, when compiled with only memoized function gridTravelerMemo(2,3) gives an address boundary error.

#include<bits/stdc++.h>
unsigned gridTraveller(unsigned m, unsigned n);
unsigned gridTravelerMemo(unsigned m, unsigned n);
std::string keyConvertedToString(unsigned m, unsigned n);

int main(int argc, char const *argv[])
{               
    //std::cout<<gridTraveller(2,3);
    std::cout<<gridTravelerMemo(2,3);
    return 0;
}

unsigned gridTraveller(unsigned m, unsigned n)
{
    if (m == 1 && n == 1) return 1;
    if (m == 0 || n == 0) return 0;
    return gridTraveller(m-1, n) + gridTraveller(m, n-1);
}

std::string keyConvertedToString(unsigned m, unsigned n)
{
    return (std::to_string(m) + ',' + std::to_string(n));
}

unsigned gridTravelerMemo(unsigned m, unsigned n)
{   
    std::unordered_map<std::string, int> memo;
    const std::string key = keyConvertedToString(m,n);
    if (memo.count(key) > 0) 
        return memo.at(key);
    memo[key] = gridTravelerMemo(m-1, n) + gridTravelerMemo(m, n-1);
    return memo.at(key);
} 

Tried printing the keys and it works, so there's probably something wrong with the line :

memo[key] = gridTravelerMemo(m-1, n) + gridTravelerMemo(m, n-1);

not sure what's it though; please anybody?

Answer 1

You need to add a breaker and initialization condition in function gridTravelerMemo

Update:

Another problem is, you are initialization unordered map every time in the gridTravelerMemo function so you need to remove this also from the function and initialize it as a global.

Code:

 #include<bits/stdc++.h>
unsigned gridTraveller(unsigned m, unsigned n);
unsigned gridTravelerMemo(unsigned m, unsigned n);
std::string keyConvertedToString(unsigned m, unsigned n);

std::unordered_map<std::string, int> memo;

int main(int argc, char const *argv[])
{
    //std::cout<<gridTraveller(2,3);
    std::cout<<gridTravelerMemo(2,3);
    return 0;
}

unsigned gridTraveller(unsigned m, unsigned n)
{
    if (m == 1 && n == 1) return 1;
    if (m == 0 || n == 0) return 0;
    return gridTraveller(m-1, n) + gridTraveller(m, n-1);
}

std::string keyConvertedToString(unsigned m, unsigned n)
{
    return (std::to_string(m) + ',' + std::to_string(n));
}

unsigned gridTravelerMemo(unsigned m, unsigned n)
{

    const std::string key = keyConvertedToString(m,n);
    if (memo.count(key) > 0)
        return memo.at(key);
    if(m==0 || n==0) return 0;
    if(m==1 && n==1) return 1;
    memo[key] = gridTravelerMemo(m-1, n) + gridTravelerMemo(m, n-1);
    return memo.at(key);
}