动态规划：使用记忆实现解决方案

Question

如问题所述，我正在尝试解决 leetcode problem。这些解决方案可在线获得，但我想实施自己的解决方案。我已经建立了我的逻辑。逻辑完全没问题。但是，我无法优化代码，因为大量的时间超过了限制。

这是我的代码：

let count = 0;

const climbingStairs = (n, memo = [{stairs: null}]) => {

if(n === memo[n]) {
    count += memo[n].stairs;
}

if(n < 0) return;

if(n === 0) return memo[n].stairs = count++;

memo[n] = climbingStairs(n - 1, memo) + climbingStairs(n - 2, memo); 

return memo[n];
}

climbingStairs(20); //running fine on time
climbingStairs(40); //hangs as the code isn't optimized

console.log(count); //the output for the given number

使用记忆对象的代码优化不起作用。我尝试了多种方法，但仍然面临问题。在优化代码方面的任何帮助将不胜感激。谢谢！

Answer 1

实际上，您存储的不是一个值，而是 NaN 到数组。

您需要 return 零来获得加法的数值。

此外，您在每次调用中都分配了一个新值，即使您已经在数组中有了这个值。

一个好主意是在数组中只使用相同的类型（对象与数字）而不是混合类型，因为您需要对每种类型进行不同的处理。

const climbingStairs = (n, memo = [1]) => {
    if (n < 0) return 0;
    return memo[n] ??= climbingStairs(n - 1, memo) + climbingStairs(n - 2, memo);
}

console.log(climbingStairs(5));
console.log(climbingStairs(20));
console.log(climbingStairs(40));

Answer 2

不需要计数值，可以这样记忆：

const climbStairs = (n, memo = []) => {
    if(n <= 2) return n;
    if(memo[n]) {
        return memo[n];
    }
   
    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo); 
    return memo[n];
}

动态规划：使用记忆实现解决方案

Dynamic Programming: Implementing a solution using memoization

javascript

memoization

dynamic-programming