C++网格不同路径DP问题中记忆化检查放在函数顶部为何失效？

记忆化查询语句的摆放位置确实会影响代码运行结果，你遇到的问题本质是数组越界访问，和记忆化逻辑本身无关，具体原因如下：

两种写法的执行流程差异 #

你定义的memo数组的合法下标范围是0 ≤ i < m、0 ≤ j < n，只有在i、j符合这个范围的时候才能访问memo的对应位置，两种写法的执行顺序差异直接决定了会不会触发越界：

写法1（记忆化放开头，运行异常） #

执行顺序：

1. 无任何前置校验，直接访问memo[i][j]
2. 再判断是否到达终点、是否越界
   问题：当递归调用传入的参数满足i ≥ m或者j ≥ n时，访问memo[i][j]已经超出了数组的合法下标范围，触发未定义行为，大概率会直接崩溃或返回错误结果。

写法2（记忆化放边界判断后，运行正常） #

执行顺序：

1. 先判断是否越界、是否到达终点，这两类非法/终止状态会直接返回结果，不会走到后续的memo访问逻辑
2. 只有i、j都处于合法范围时，才会执行记忆化查询，完全不会出现越界问题

补充优化建议 #

• 记忆化读写操作必须放在边界校验之后，保证只有合法状态才会读写缓存
• 你当前代码的返回值为int类型，当网格规模稍大时路径总数会超出int的取值范围，建议将返回值改为long long避免溢出。

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