LeetCode动态规划超时疑问：Object缓存为何不如二维数组？

我在LeetCode解决「分割等和子集」问题时，发现用Object作为记忆化缓存会触发“Time limit exceeded”超时错误，但换成预初始化的二维数组缓存后，代码就能正常通过。

Object缓存版本（超时） #

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    var sum = nums.reduce((accumulator, currentValue) => {
  return accumulator + currentValue
},0);
console.log(sum/ 2)

    if(sum % 2 === 0) {
       return checkIfPart(0, Number(sum/2), nums, {})
    }
    return false
};

var checkIfPart  = function(currentIndex, currentWeight, nums, obj) {
    if (obj && currentIndex in obj  && currentWeight in obj[currentIndex]) {
        return  obj[currentIndex][currentWeight]
    }
    if (currentWeight === 0) {
        return true
    }
    if (currentIndex >= nums.length || currentWeight < 0) {
        return false
    }
   console.log(nums[currentIndex])
    let put = checkIfPart(currentIndex + 1, currentWeight - nums[currentIndex], nums, obj)
    let notPut = checkIfPart(currentIndex+ 1, currentWeight, nums, obj)
    if (!obj[currentIndex]) {
        obj[currentIndex] = {}
    }
    obj[currentIndex][currentWeight] =  put || notPut
    return put || notPut
}

二维数组缓存版本（通过） #

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
//     var sum = nums.reduce((accumulator, currentValue) => {
//   return accumulator + currentValue
// },0);
const n =nums.length
 let sum = 0
 for(let i=0; i<n; i++){
        sum += nums[i];
    }
    if(sum % 2 === 0) {
       
        var obj = new Array(n+1).fill(-1).map(() => new Array(sum/2+1).fill(-1));
       return checkIfPart(0, Number(sum/2), nums, obj)
    }
    return false
};

var checkIfPart  = function(currentIndex, currentWeight, nums, obj) {
    if (obj[currentIndex][currentWeight] != -1) {
        return  obj[currentIndex][currentWeight]
    }
    if (currentWeight === 0) {
        return true
    }
    if (currentIndex >= nums.length || currentWeight < 0) {
        return false
    }
    let put = checkIfPart(currentIndex + 1, currentWeight - nums[currentIndex], nums, obj)
    let notPut = checkIfPart(currentIndex+ 1, currentWeight, nums, obj)
   
    obj[currentIndex][currentWeight] =  put || notPut
    return put || notPut
}

为什么Object缓存会超时？ #

1. 属性检查的性能损耗

数组的索引访问是直接内存寻址，速度极快；而in运算符需要遍历对象的属性链（包括原型链）来判断属性是否存在，每次判断都有额外开销。对于递归次数极多的动态规划问题，这种累积的损耗会直接导致超时。你代码里两次in判断，每轮递归都要执行，在大规模测试用例下会消耗大量时间。

2. 动态创建对象的额外开销

Object版本中，每次缓存结果都要先判断obj[currentIndex]是否存在，不存在则创建新对象。这种动态分配内存的操作，相比数组预分配内存的方式，会带来更高的内存分配和垃圾回收压力，拖慢执行速度。

3. 冗余的边界判断

代码里的obj && currentIndex in obj是冗余的——缓存对象obj是一开始传入的空对象，不可能为null或undefined，这部分判断完全没必要，属于额外的性能浪费。

4. 数组的缓存效率更高

二维数组是预初始化好的，所有缓存位置都提前分配了内存，命中时直接通过索引取值；而Object是动态添加属性，JS引擎对动态对象的属性访问优化远不如数组高效，尤其是在频繁读写的场景下。

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