Why is my Grid Traveler Memoization still sticking?-CodePudding

I'm currently working on implementing memoization into the Grid Traveler problem. It looks like it should work, but it's still sticking on bigger cases like (18,18). Did I miss something, or are maps not the right choice for this kind of problem?

P.S. I'm still very new at working with maps.

    #include <iostream>
    #include <unordered_map>
    #include <string>
    using namespace std;

    uint64_t gridTravMemo(int m, int n, unordered_map<string, uint64_t>grid)
    {
        string key;

        key = to_string(m)   ","   to_string(n);
        if (grid.count(key) > 0)
            return grid.at(key);
        if (m == 1 && n == 1)
            return 1;
        if (m == 0 || n == 0)
            return 0;

        grid[key] = gridTravMemo(m-1, n, grid)   gridTravMemo(m, n-1, grid);
        return grid.at(key);
    }

    int main()
    {
        unordered_map<string, uint64_t> gridMap;

        cout << gridTravMemo(1, 1, gridMap) << endl;
        cout << gridTravMemo(2, 2, gridMap) << endl;
        cout << gridTravMemo(3, 2, gridMap) << endl;
        cout << gridTravMemo(3, 3, gridMap) << endl;
        cout << gridTravMemo(18, 18, gridMap) << endl;

        return 0;
    }

CodePudding user response：

The point of memorized search is to optimize running time by returning any previous values that you have calculated. This way, instead of a brute force algorithm, you can reach a runtime of O(N*M).

However, you are passing your unordered_map<string, uint64_t>grid as a parameter for your depth-first search.

You are calling grid[key] = gridTravMemo(m-1, n, grid) gridTravMemo(m, n-1, grid); This means that your search is splitting into two branches. However, the grid in these two branches are different. This means that the same state can be visited in two separate branches, leading to a runtime more like O(2^(N*M)).

When you're testing an 18x18 grid, this definitely will not run quickly enough.

This is relatively easy to fix. Just declare grid as a global variable. This way its values can be used between different branches.

Try something like this:

    #include <iostream>
    #include <unordered_map>
    #include <string>
    using namespace std;

    unordered_map<string, uint64_t> grid;

    uint64_t gridTravMemo(int m, int n)
    {
        string key;

        key = to_string(m)   ","   to_string(n);
        if (grid.count(key) > 0)
            return grid.at(key);
        if (m == 1 && n == 1)
            return 1;
        if (m == 0 || n == 0)
            return 0;

        grid[key] = gridTravMemo(m-1, n)   gridTravMemo(m, n-1);
        return grid.at(key);
    }

    int main()
    {

        cout << gridTravMemo(1, 1) << endl;
        grid.clear()
        cout << gridTravMemo(2, 2) << endl;
        grid.clear()
        cout << gridTravMemo(3, 2) << endl;
        grid.clear()
        cout << gridTravMemo(3, 3) << endl;
        grid.clear()
        cout << gridTravMemo(18, 18) << endl;

        return 0;
    }