动态编程:使用记忆实现解决方案

Question

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

这是我的代码：

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

不需要计数值，可以通过以下方式进行记忆：

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];
}

Answer 2

实际上，您不存储值，而是将NaN存储到数组中。

您需要返回零以获得用于相加的数值。

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

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

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));