带停靠点的1/2/3步跳路径计数问题求解及代码疑问

问题定义澄清 #

首先明确核心概念：A到B之间有n个停靠点，意味着所有点的序列是 A = P₀, P₁, P₂, ..., Pₙ, Pₙ₊₁ = B。每次跳跃可以从当前点跳到下1个、下2个或下3个点（即单次跳1步、2步、3步，不能超过B点）。我们要求的是从P₀到Pₙ₊₁的路径总数。

这个问题完全等价于经典爬楼梯问题的变种：爬m = n+1阶台阶，每次可以爬1、2、3阶，求爬到第m阶的路径数。

基础用例纠正 #

你之前的基础用例推导存在矛盾，这里给出正确的基础用例：

• n=0（无停靠点，直接A到B）：对应m=1阶台阶，只有1种路径（直接跳1步），路径数=1
• n=1（1个停靠点）：对应m=2阶台阶，有2种路径：A→停靠点→B（两次跳1步）、A→B（跳2步），路径数=2
• n=3（3个停靠点）：对应m=4阶台阶，路径数=7，和你实际数的一致，具体路径为：
  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

递归代码错误分析 #

你算出n=3时结果为6，说明递归的基础条件定义错误，或者递归公式对应关系搞错了。

正确的递推逻辑 #

设f(m)为爬m阶台阶（对应n=m-1个停靠点）的路径数：

• 递推公式：f(m) = f(m-1) + f(m-2) + f(m-3)
  解释：到达第m阶的最后一步，只能是从m-1阶跳1步、m-2阶跳2步、m-3阶跳3步，所以总路径数是这三种情况的和。
• 基础条件：
  • f(0) = 1：到达第0阶（起点）的路径数为1（空路径，作为递归的基础）
  • f(1) = 1：只能从第0阶跳1步到达
  • f(2) = 2：从第0阶跳2步，或从第1阶跳1步

如果你的代码把f(0)设为0，那么计算f(4)时会得到f(3)+f(2)+f(1) = (f(2)+f(1)+f(0)) + f(2)+f(1) = (2+1+0)+2+1=6，刚好是你得到的错误结果——这就是问题所在！

正确的JavaScript实现 #

递归（带记忆化，避免重复计算） #

const countPaths = (n) => {
  const m = n + 1; // 转换为爬m阶台阶的问题
  const memo = new Map();
  
  const helper = (step) => {
    if (step === 0) return 1;
    if (step === 1) return 1;
    if (step === 2) return 2;
    if (memo.has(step)) return memo.get(step);
    
    const res = helper(step - 1) + helper(step - 2) + helper(step - 3);
    memo.set(step, res);
    return res;
  };
  
  return helper(m);
};

// 测试用例
console.log(countPaths(0)); // 1
console.log(countPaths(1)); // 2
console.log(countPaths(3)); // 7

迭代版本（更高效，无栈溢出风险） #

const countPaths = (n) => {
  const m = n + 1;
  if (m === 0) return 1;
  if (m === 1) return 1;
  if (m === 2) return 2;
  
  let a = 1; // f(0)
  let b = 1; // f(1)
  let c = 2; // f(2)
  
  for (let i = 3; i <= m; i++) {
    const next = a + b + c;
    a = b;
    b = c;
    c = next;
  }
  
  return c;
};

// 测试用例
console.log(countPaths(0)); // 1
console.log(countPaths(1)); // 2
console.log(countPaths(3)); // 7

内容的提问来源于stack exchange，提问作者ABGR