经典题解析：10 个节点的环上走 N 步回到原点，共有多少种走法

图 1：本文封面，10 个节点的环与「状态 × 步数」的计数思路。

先说明属性：这是一篇经典题解析，题目出自本地历史面试资料，与任何公司的当前招聘无关。题面很短：编号 0 到 9 的十个节点围成一个环，从 0 号出发，每一步必须向左或向右走一格，走 N 步恰好回到 0 号节点，共有多少种走法？这道题考的不是走路，而是你能不能把「指数级路径」压缩成「常数个状态」。

先看暴力为什么出局：2 的 N 次方条路。

每步只有向左、向右两种选择，N 步就是 2 的 N 次方条路径。N 等于 10 时不过 1024 条，还能硬数；N 等于 40 就是约一万亿条，枚举直接出局。但注意一个关键事实：你真正关心的不是「路径长什么样」，而是「第 n 步走完时停在哪个节点」。路径有指数条，位置却只有 10 个——所有「走了 n 步后停在 i 号」的路径，对下一步而言完全等价。这就是动态规划的入口：把等价的路径合并计数。

定义状态并推出转移方程。

设 dp[n][i] 表示走 n 步恰好停在 i 号节点的走法总数。想让第 n 步停在 i，上一步必须站在 i 的两个邻居之一：左邻居 (i-1+10) mod 10，右邻居 (i+1) mod 10。而从邻居走到 i 的那一步是确定的，不引入新的分支，所以：

dp[n][i] = dp[n-1][(i-1+10) mod 10] + dp[n-1][(i+1) mod 10]

初始条件是 dp[0][0] = 1：一步都不走时必然在 0 号，算一种方案，其余 dp[0][i] 全为 0。最终答案就是 dp[N][0]。注意环形的头尾相接全部交给 mod 10 处理，9 号的右邻居自然绕回 0 号，不需要任何 if 特判——这是环形问题与直线问题唯一的差别。

手算前几行，把直觉坐实。

n=1 时，从 0 只能走到 1 或 9，所以 dp[1][1] 与 dp[1][9] 各为 1，dp[1][0] 为 0。n=2 时，回到 0 有两条路（0→1→0 与 0→9→0），同时 2 号和 8 号各有 1 条。继续按公式填表，n=3 时 1 号与 9 号各涨到 3，n=4 时 dp[4][0] 等于 6。这张表还藏着一个免费结论：每走一步，编号的奇偶性必然翻转，0 是偶数，所以 N 为奇数时 dp[N][0] 恒为 0——填表填到一半就能发现这个规律，考场上说出来是加分项。

代码实现，并用暴力枚举对拍。

下面用 Node.js 22.15.0 实现递推，再用枚举全部 2 的 N 次方条路径的暴力法对小 N 对拍（node ring-walk.js）：

'use strict';
// 10 个节点的环（编号 0~9），每步向左或向右一格，走 n 步恰好回到 0 的方案数
function countWays(n) {
  const M = 10;
  let dp = new Array(M).fill(0);
  dp[0] = 1; // 走 0 步时必然在 0 号
  for (let step = 1; step <= n; step++) {
    const next = new Array(M).fill(0);
    for (let i = 0; i < M; i++) {
      next[i] = dp[(i - 1 + M) % M] + dp[(i + 1) % M];
    }
    dp = next;
  }
  return dp[0];
}
// 暴力对拍：枚举全部 2^n 条路径
function brute(n) {
  let cnt = 0;
  for (let mask = 0; mask < (1 << n); mask++) {
    let pos = 0;
    for (let s = 0; s < n; s++) pos = (pos + ((mask >> s) & 1 ? 1 : -1) + 10) % 10;
    if (pos === 0) cnt++;
  }
  return cnt;
}
for (const n of [2, 4, 10]) console.log(`n=${n}: DP=${countWays(n)}, 暴力=${brute(n)}`);
console.log('n=3（奇数步）:', countWays(3));
console.log('n=40:', countWays(40));

实测输出：

n=2: DP=2, 暴力=2
n=4: DP=6, 暴力=6
n=10: DP=254, 暴力=254
n=3（奇数步）: 0
n=40: 219993856006

三个信息点：DP 与暴力在 N=2、4、10 上完全一致，转移方程的正确性被对拍坐实；N=3 输出 0，验证了奇偶性结论；N=40 算出 219993856006，暴力法在这个规模下根本跑不完，而 DP 只做了 40×10 次加法。时间复杂度 O(N×10)，空间上每一轮只依赖上一轮，用两个数组滚动即可压到 O(10)。

图 2：DP 表逐行展开，dp[4][0]=6 就是这么填出来的。

往深走一步：这和马尔可夫链是同一套骨架。

把「位置」看成状态、「走一步」看成一次状态转移，这道题就是在数一个马尔可夫链经过 N 次转移回到起点的路径条数。矩阵形式下，答案就是转移矩阵的 N 次幂左上角那个元素——如果面试官追问「N 很大怎么办」，快速幂可以把时间压到 O(log N) 量级。从合并等价路径到状态转移矩阵，计数题与序列建模共享的正是这套「状态 × 步数」的骨架。

回到面试现场，建议的答题结构：先说暴力的指数代价，引出「只关心位置、合并等价路径」的状态定义；写出转移方程与初始条件，强调环形边界用取模统一处理；手算一两行表格建立信任；最后主动补奇偶性结论与滚动数组优化，有追问再谈矩阵快速幂。方程是及格线，奇偶观察和复杂度讨论是加分项。这类「状态 × 步数」的递推题，你还见过哪些印象深刻的变体？欢迎在评论区聊聊。