C++记忆化递归实现2D网格路径计数出现地址边界错误求助

你标注的memo[key] = gridTravelerMemo(m-1, n) + gridTravelerMemo(m, n-1);一行本身语法无错误，触发地址边界错误是两个上下文逻辑缺陷共同导致的：

• 缺失递归终止条件
  记忆化版本完全丢失了无记忆化实现的两个边界判断逻辑：

  if (m == 1 && n == 1) return 1;
  if (m == 0 || n == 0) return 0;
  没有终止条件的递归会无限向下调用，unsigned类型的行/列参数减到0后继续减会触发无符号整数溢出，变为极大值，最终引发内存访问越界。

• 记忆化缓存为局部变量
  当前std::unordered_map<std::string, int> memo是函数局部变量，每次递归调用都会创建全新的空map，之前的计算结果完全无法复用，记忆化逻辑完全失效。

修复方案 #

把缓存通过引用传递到递归函数，同时补全终止条件即可，修复后代码如下：

#include<bits/stdc++.h>
unsigned gridTravelerMemo(unsigned m, unsigned n, std::unordered_map<std::string, unsigned>& memo);
std::string keyConvertedToString(unsigned m, unsigned n);

int main(int argc, char const *argv[])
{               
    std::unordered_map<std::string, unsigned> memo;
    std::cout << gridTravelerMemo(2, 3, memo);
    return 0;
}

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, unsigned>& memo)
{   
    // 补全递归终止条件
    if (m == 1 && n == 1) return 1;
    if (m == 0 || n == 0) return 0;
    const std::string key = keyConvertedToString(m, n);
    if (memo.count(key)) 
        return memo.at(key);
    memo[key] = gridTravelerMemo(m-1, n, memo) + gridTravelerMemo(m, n-1, memo);
    return memo.at(key);
} 

可选优化 #

可以直接用std::pair<unsigned, unsigned>作为unordered_map的键，省去字符串拼接的开销；如果不需要多次调用函数，也可以把缓存设为函数内静态变量，简化传参逻辑。

内容的提问来源于stack exchange，提问作者rutuja