以 n 步到达四面体中的顶点 d

Question

我正在解决这个问题：

给定一个具有顶点 A、B、C 和 D 的四面体。一只蚂蚁站在顶点 D 处。蚂蚁不会闲着。它将沿着四面体的某些边缘不断从一个顶点移动到另一个顶点。你的任务是计算蚂蚁从初始顶点 D 到自身的路径数，正好是 n 步。

所以对于输入 2 输出 ： 3

我能够按照以下方式使用递归轻松解决这个问题。但对于大输入（例如 15）来说，由于其时间复杂度，它似乎效率不高。

这可以通过动态编程来解决，但我在当前的方法中没有看到任何记忆范围。也许我需要改变方法。非常感谢任何帮助。

我想用递归+记忆来解决它

var count = 0;
function recursion(n, arr=['d']){
    if(n <=1) return 0;
  
  if(arr.length === n+1 && arr[arr.length-1] ==='d'){
    console.log(arr.join(" -> "))
    count++;
    return;
  }

  if(arr.length > n+1) return;

  for(let el of ['a', 'b', 'c', 'd']){
    if(arr[arr.length-1] != el){
       recursion(n, [...arr, el]);
    }
  }
}
recursion(3)

console.log(count);

Answer 1

你确实可以在这里使用记忆功能。

首先我们来分析一下递归关系。

定义：

• 𝑆_𝑛 是从顶点到自身的长度为 𝑛 的路径数。

• 𝐷_𝑛 是从一个顶点到选定的不同 的长度为𝑛 的路径数。我们选择哪个目标顶点并不重要，因为四面体是完全对称的。

现在递归关系：

要递归地获取到原始顶点 (𝑆_𝑛) 的长度为 𝑛 的路径数，您可以从三个邻居中选择一个邻居，然后计算从那里回到起始顶点的（较短）路径的数量，即由𝐷给出。所以：

      𝑆_𝑛 = 3𝐷_𝑛−1

要递归地获取到不同顶点（𝐷_𝑛）的长度为𝑛的路径数，您可以选择that邻居并计算从那里到自身的（较短）路径的数量，或者您可以选择其他两个邻居之一，并计算从那里到目标顶点的（较短）路径的数量。所以：

      𝐷_𝑛 = 𝑆_𝑛−1 + 2𝐷_𝑛−1

后一个方程可以通过替换到这个方程来展开：

      𝐷_𝑛 = 3𝐷_𝑛−2 + 2𝐷_𝑛−1

当我们引用 𝑛−2 时，我们需要至少两个基本情况：

• 𝐷₀ = 0（没有大小为 0 的路径将您带到另一个顶点）
• 𝐷₁ = 1（从一个顶点到另一个顶点有一条大小为 1 的路径）

实施

由于𝐷有一个很好的递归关系，我们可以首先实现一个函数，返回从一个顶点到另一个顶点的路径数。然后使用第一个递归关系将原始查询（指向 same 顶点的路径数）转换为该问题：

// Memoize the number of paths from one vertex to a different one
const memo = new Map().set(0, 0).set(1, 1);

function numPathsToOther(size) {
    if (!memo.has(size)) {
        memo.set(size, 3*numPathsToOther(size-2) + 2*numPathsToOther(size-1));
    }
    return memo.get(size);
}

function numPathsToSelf(size) {
    return size ? 3 * numPathsToOther(size - 1) : 1;
}

// Demo runs for the first few path-sizes:
for (let i = 0; i <= 10; i++) {
    console.log(i, numPathsToSelf(i));
}