01背包问题2D Vector记忆化搜索超时但2D数组通过的原因咨询

两段代码性能差异的具体原因如下： #

• 内存布局与CPU缓存效率差距
  正常运行的代码中，int dp[1005][1005]是全局静态二维数组，编译阶段就会分配连续的内存空间，访问dp[i][wght]时可以直接通过基地址+偏移量计算得到目标地址，连续的内存结构对CPU缓存非常友好，相邻访问的缓存命中率极高，寻址开销极低。
  而触发TLE的代码使用vector<vector<int>>作为dp容器，嵌套vector的内存并不连续：每个内层vector<int>都是独立在堆上分配的内存块，访问dp[i][wght]需要先寻址找到第i个内层vector的起始地址，再寻址找到对应下标wght的元素，两次指针跳转本身开销更大，且非连续内存会导致CPU缓存命中率大幅下降，在递归高频访问dp的场景下性能差距会被成倍放大。
• 初始化操作的效率差距
  触发TLE的代码初始化dp时，vector<vector<int>> dp(1005, vector<int> (1005 , -1))需要先完成1005次内层vector的堆内存分配，再逐个为1005*1005的元素赋值-1，多次内存分配+逐元素赋值的开销很高。
  正常运行的代码使用memset(dp , -1 , sizeof(dp))初始化连续的全局数组，memset是底层做过指令级优化的字节批量赋值操作，针对连续大块内存的赋值效率远高于嵌套vector的初始化逻辑。
• 额外优化建议：两段代码的递归函数都采用值传递的方式传入vector<pair<int,int>> a，每次递归调用都会完整复制一遍a数组，本身也会带来不小的额外开销，建议修改为const vector<pair<int,int>>& a传引用，可以进一步降低运行耗时。

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