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];
}
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.