如果我在函数顶部切换注释行的位置，为什么我的代码不起作用？这是一个记忆回忆声明

Question

我正在尝试记住这个独特的路径网格问题。直到现在，我总是将记忆化的 return 语句放在函数之上。但在这里，它不起作用。我不明白为什么。

这些职位有时重要吗？能解释一下原因吗？

我刚开始动态规划。

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

Answer 1

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

在这里，您首先检查 if (i >= m || j >= n)，以防止越界错误，然后再尝试访问 memo[i][j];

但是：

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

在这里，您先尝试访问 memo[i][j];，然后再检查 if (i >= m || j >= n) return 0;，因此此处可能会发生越界错误，您会得到 未定义的行为.

如果我在函数顶部切换注释行的位置，为什么我的代码不起作用？这是一个记忆回忆声明

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

c++

recursion

dynamic-programming

memoization