LeetCode 补充题 2. 圆环回原点问题
目录
题目描述
✅ 补充题 2. 圆环回原点问题
题意分析
圆环上按顺时针依次排布 10 个点，编号
0到9。从0号点出发，每一步只能走到相邻的点（向左一格或向右一格），问恰好走n步之后重新停在0号点，一共有多少种走法。题目里有几个信号需要读准。
第一，「恰好
n步」而不是「至多n步」。中途经过原点不算数，也不能提前停下，步数必须用满，所以这是一个按步数分层的计数问题，而不是最短路或可达性问题。第二，「向左或向右」意味着每一步都有且只有两种选择，
n步的全部走法共2^n条。答案是这些走法中终点为0的那一部分，所以答案上界是2^n，规模随n指数增长，逐条枚举路径显然不现实。第三，圆环是首尾相连的。
0号点的左边不是「越界」，而是9号点；9号点的右边则回到0号点。这条环形性质是这道题区别于普通爬楼梯类计数的核心，处理不当就会数组越界或漏算走法。边界上要注意两点：
n = 0时人还在原点，方案数是1（空走法也是一种走法）；n为奇数时答案必为0，因为圆环长度10是偶数，把点按奇偶染色后每走一步必然改变颜色，奇数步无法回到同色的起点。这个奇偶性可以作为验算结论正确与否的快速自检。
解法：圆环位置动态规划
核心思路
问题关键：枚举
n步的左右选择有 $2^n$ 条路径，但很多路径会在同一步到达同一位置；从此处出发的后续结果只与“步数、位置”有关，重复搜索可以合并。为什么选动态规划：令
dp[pos]表示走完当前步数后停在pos的方案数。初始时只有空走法，故dp[0] = 1。下一步到达pos，最后一步只能来自它的两个邻点：
next[pos] = dp[(pos - 1 + 10) % 10] + dp[(pos + 1) % 10]每轮只依赖上一轮，因此两个长度为 10 的数组即可，无需保存整张二维表。
状态不变量：第
step轮结束后，dp[pos]恰好是不多不少走step步到达pos的方案数；同一轮所有位置的方案数之和为 $2^{step}$。正确性：任意一条到达
pos的路径，最后一步必定从左邻点或右邻点走来，二者互斥且覆盖所有可能，所以转移不重不漏。由dp[0] = 1归纳到第n轮，dp[0]就是恰好n步回到原点的方案数。
解题步骤
- 建立长度为 10 的
dp，设置dp[0] = 1，表示零步时只在原点有一种方案。- 每走一步都新建
next，遍历 10 个位置，把上一轮两个邻点的方案数相加。- 用
(pos - 1 + 10) % 10和(pos + 1) % 10连接圆环首尾。- 一轮结束后令
dp = next；完成n轮后返回dp[0]。口述样例：
n = 4时，原点方案数依次为1、0、2、0、6，最终答案为6；它对应两次向左、两次向右的 6 种排列。
代码实现
class Solution {
private static final int SIZE = 10;
public int backToOrigin(int n) {
int[] dp = new int[SIZE];
dp[0] = 1;
for (int step = 1; step <= n; step++) {
int[] next = new int[SIZE];
for (int pos = 0; pos < SIZE; pos++) {
int left = (pos - 1 + SIZE) % SIZE;
int right = (pos + 1) % SIZE;
next[pos] = dp[left] + dp[right];
}
dp = next;
}
return dp[0];
}
}
func backToOrigin(n int) int {
const size int = 10
dp := make([]int, size)
dp[0] = 1
for step := 1; step <= n; step++ {
next := make([]int, size)
for pos := 0; pos < size; pos++ {
left := (pos - 1 + size) % size
right := (pos + 1) % size
next[pos] = dp[left] + dp[right]
}
dp = next
}
return dp[0]
}
复杂度分析
- 时间复杂度：$O(n)$，每一步固定计算 10 个位置；若环长为
m，则为 $O(nm)$。- 空间复杂度：$O(1)$，两个数组长度固定为 10；若环长为
m，则为 $O(m)$。
关键点总结
- “恰好走
step步到达pos”必须同时包含步数和位置，不能只记录是否到过。- 滚动数组必须分成
dp和next，保证本轮只读上一轮。- 状态总和应为 $2^{step}$，可用来快速检查是否漏算或重复计数。
- 10 是偶数，因此奇数步必然回不到原点；这是校验结论，不是 DP 正确性的前提。
- 若题目要求取模，应在每次加法时取模；当前题意未给模数，不自行添加。
易错点总结
- Java 和 Go 的负数取模仍可能为负，左邻点必须写成
(pos - 1 + SIZE) % SIZE。- 不能原地更新
dp：后算的位置会读到本轮新值。n = 2可快速暴露污染。dp[0]必须初始化为 1，零步不动也是一种合法走法；否则所有状态永远为 0。- 滚动后数组下标表示“位置”，最终返回
dp[0]，不是dp[n]。- 方案数最多按 $2^n$ 增长；若约束较大，需按题意改用更宽整数或取模。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 70. 爬楼梯 | 简单 | 状态只有一维台阶数，路径单向不回头，无需环形取模 |
| 509. 斐波那契数 | 简单 | 递推式直接给定，练滚动变量替代数组的最小模型 |
| 746. 使用最小花费爬楼梯 | 简单 | 转移从「求和计数」换成「取最小值」，同构不同聚合 |
| LCR 088. 使用最小花费爬楼梯 | 简单 | 746 的同题改编，可对照两种起点初始化写法 |
| 剑指 Offer 10- I. 斐波那契数列 | 简单 | 强制对 1e9 + 7 取模，练计数 DP 的溢出处理 |
| 剑指 Offer 10- II. 青蛙跳台阶问题 | 简单 | 初始条件与 70 略有差异，考察边界项的精确定义 |
| 面试题 08.01. 三步问题 | 简单 | 每步三种选择，转移项从两项扩到三项 |
| 62. 不同路径 | 中等 | 二维网格上的路径计数，状态两维但方向受限不成环 |