Search code examples
c++recursiondynamic-programmingmemoization

Why does my code not work if I switch the position of commented line on top of the function? It's a memoization recall statement


I'm trying to memoize this unique paths grid problem. Until now, I always put the memoized return statement on top of the function. But here, it's not working. I don't understand why.

Do those positions matter sometimes? Can you please explain the reason?

I have just started dynamic programming.

int grid(long long i, long long j, long long m, long long n, vector<vector<long long>> &memo) {
    if (memo[i][j] != -1) return memo[i][j]; // but not working here, WHY??
    if (i == m - 1 && j == n - 1) return 1; 
    if (i >= m || j >= n) return 0;
    // if (memo[i][j] != -1) return memo[i][j]; // works here
    memo[i][j] = grid(i + 1, j, m, n, memo) + grid(i, j + 1, m, n, memo);
    return memo[i][j];
}

Solution

  • int grid(long long i, long long j, long long m, long long n, vector<vector<long long>> &memo) {
        // delete the first statement
        if (i == m - 1 && j == n - 1) return 1; 
        if (i >= m || j >= n) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        memo[i][j] = grid(i + 1, j, m, n, memo) + grid(i, j + 1, m, n, memo);
        return memo[i][j];
    }
    

    In here, you check that if (i >= m || j >= n) first, to prevent out-of-bounds error, before you try to access memo[i][j];

    But:

    int grid(long long i, long long j, long long m, long long n, vector<vector<long long>> &memo) {
        if (memo[i][j] != -1) return memo[i][j]; 
        if (i == m - 1 && j == n - 1) return 1; 
        if (i >= m || j >= n) return 0;
        // delete the second statement
        memo[i][j] = grid(i + 1, j, m, n, memo) + grid(i, j + 1, m, n, memo);
        return memo[i][j];
    }
    

    In here, you try to access memo[i][j]; first, before you check if (i >= m || j >= n) return 0;, so an out-of-bounds error could happen here, and you get undefined behaviour.