DP 解决方案未正确缓存 - 输入为 ~70 时出现超时错误

Question

我正在尝试解决这个问题：https://leetcode.com/problems/divisor-game/

我的递归本身似乎有效，但当输入足够大时出现超时错误 ~ 70。我尝试进行记忆以缓存以前的解决方案，但由于某种原因它似乎不起作用。我不知道为什么。

 /**
     * @param {number} n
     * @return {boolean}
     */
    var divisorGame = function(n) {
       return helper(n);
    };
    
    const helper = (n, cache = {}) => {
        if(n === 1) return false;
        if(n in cache) return cache[n];
      
        
        for(let i = 0; i < n; i++) {
            if(n % i === 0) {
                if(helper(n - 1) === false) return cache[n] = true;
            } 
        }
        
        return cache[n] = false;
        
    }

Answer 1

您遇到的问题是：

从 i = 0 开始循环，而问题明确表示 0 < i < n。
问题说选择i后，需要将当前的n替换为n - i，但你调用的是helper(n-1)。

下面是修复了上述错误的AC代码的实现。

var divisorGame = function(n) {
   return helper(n);
};

const cache = [];

function helper(n){
    if(n === 1) return false;
    if(n in cache) return cache[n];

    for(let i = 1; i < n; i++) {
        if(n % i === 0) {
            if(helper(n-i) == false){
                return cache[n] = true;
            }
        } 
    }
    return cache[n] = false;
}

DP 解决方案未正确缓存 - 输入为 ~70 时出现超时错误

DP Solution Not Caching Properly - Time Out Error when input is ~70

javascript

algorithm

optimization

recursion

dynamic-programming