javaScript 动态规划

Question

我正在学习如何使用记忆，但遇到了这个问题

const memo = {
  0: 0,
  1: 0,
  2: 1
};

function tribonacci(n, memo) {
  // DO NOT CHANGE THE NEXT FOUR LINES
  if (n in memo) return memo[n];
  const n1 = tribonacci(n - 1)
  const n2 = tribonacci(n - 2)
  const n3 = tribonacci(n - 3)
  // DO NOT CHANGE THE PREVIOUS FOUR LINES

  // Your code here
  if (n === 1 || n === 2) return 1;
  memo[n] = n1 + n2 + n3;
  return memo[n];
}

console.log(tribonacci(3));

但它给了我 2 个错误。它说“不能在未定义的 3 运算符中使用”和“不能在未定义的运算符中使用来搜索 30”，我不知道出了什么问题。

Answer 1

您的代码存在两个主要问题：

您创建了一个始终为 undefined 的局部参数 memo（除非您将其作为参数传递给函数调用），并遮盖了文件范围 memo 变量.只需删除它即可修复您报告的错误。
您的终端案例通常必须在递归的开头。否则你会得到一个无限循环。在再次调用 tribonacci 之前将第二个 if 向上移动。

可能还有更多问题，但这肯定是两个大问题。

Answer 2

所以我对它进行了一些重构，现在它看起来像这样，但它没有再次通过，它说 tribonacci 不是一个函数

// const memo = {0: 0, 1: 0, 2: 1};
function tribonacci(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n === 1 || n === 2) return 1;
  // DO NOT CHANGE THE NEXT FOUR LINES
  const n1 = tribonacci(n - 1);
  const n2 = tribonacci(n - 2);
  const n3 = tribonacci(n - 3);
  // DO NOT CHANGE THE PREVIOUS FOUR LINES

  // Your code here
  memo[n] = (n1, memo) + (n2, memo) + (n3, memo);
  return memo[n];
}

我确定他们可能希望我使用我注释掉的备忘录对象，但我不确定

Answer 3

给你，

function tribonacci(n = 0, memo = {}) {
  if (memo[n]) return memo[n];
  if (n < 2) return 1;

  const $n1 = n - 1;
  const $n2 = n - 2;
  const $n3 = n - 3;

  const n1 = memo[$n1] || tribonacci($n1, memo)
  const n2 = memo[$n2] || tribonacci($n2, memo)
  const n3 = memo[$n3] || tribonacci($n3, memo)

  memo[n] = n1 + n2 + n3;

  return memo[n];
}

console.log(tribonacci(3));

Answer 4

您需要删除函数定义中的参数。

const memo = {
  0: 0,
  1: 0,
  2: 1
};

function tribonacci(n) {
  // DO NOT CHANGE THE NEXT FOUR LINES
  if (n in memo) return memo[n];
  const n1 = tribonacci(n - 1)
  const n2 = tribonacci(n - 2)
  const n3 = tribonacci(n - 3)
  // DO NOT CHANGE THE PREVIOUS FOUR LINES

  // Your code here
  if (n === 1 || n === 2) return 1;
  memo[n] = n1 + n2 + n3;
  return memo[n];
}

console.log(tribonacci(3));

这里是计算斐波那契数列的完整版本。

const memo = {
  0: 0,
  1: 0,
  2: 1
};

function fibonacci(n) {
  if (n in memo) return memo[n];
  if (n === 1 || n === 2) return 1
  memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
  return memo[n]
}

console.log(fibonacci(10));
console.log(memo)

javaScript 动态规划

javaScript dynamic programming

javascript

dynamic-programming