1

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).

visualization of the function gridTraveller(2,3)

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?

hrutuja
  • 55
  • 3
  • 1
    You don't need dynamic programming for this. You need to make `m+n-2` steps of which `m-1` are down; these can be done in any order. So the answer is `C(m+n-2, m-1)` where `C` is [the binomial coefficient](https://en.wikipedia.org/wiki/Binomial_coefficient) – Igor Tandetnik Aug 22 '21 at 14:15
  • 1
    your `gridTravelerMemo` doesn't share the memory. (most likely not relate to "boundary error" though) – apple apple Aug 22 '21 at 14:18
  • 1
    `memo` is a local variable in `gridTravelerMemo`; every invocation of `gridTravelerMemo` gets its own copy. `memo.count(key)` is always zero since `memo` is always empty. – Igor Tandetnik Aug 22 '21 at 14:19
  • 1
    You don't have the terminal conditions of `m == 1 && n == 1` and `m == 0 || n == 0`, the way you do in `gridTraveller`. You keep subtracting 1 from `m` and `n` until eventually they wrap around to a huge value; then you keep walking until stack overflow. – Igor Tandetnik Aug 22 '21 at 14:23
  • @IgorTandetnik memo is now made to be global and the function gridTravelerMemo() is made to be static, the address boundary error still persists. And yes, your other binomial coefficient solution works. – hrutuja Aug 22 '21 at 14:31
  • Again, you need to terminate the recursion for small `m` and `n`, the way you do in `gridTraveller`. As written, you are eventually calling `gridTravellerMemo(UINT_MAX, ...)`, and it's a looong way down from there. – Igor Tandetnik Aug 22 '21 at 14:33
  • @IgorTandetnik the error is resolved after adding exactly those terminal conditions after return memo.at(key); And, the code works fine now, thanks. – hrutuja Aug 22 '21 at 14:37

1 Answers1

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);
}
Rituraj Singh
  • 26
  • 3