LeetCode 补充题 2. 圆环回原点问题
题目描述
:::fold-green 相关原题
✅ 圆环回原点
牛客原题要求对 10^9 + 7 取模，本文保留不取模版本。
:::
圆环上有
10个点，依次编号为0到9，其中0和9也相邻。给定非负整数
n，从点0出发，每一步可以顺时针或逆时针移动到相邻点。请返回恰好移动n步后回到点0的不同走法数量。只要某一步的移动方向不同，就视为不同走法。
示例 1：
输入：n = 2
输出：2
解释：两种走法为 0 → 1 → 0 和 0 → 9 → 0。
提示：
- 每一步必须移动，不能停留在当前点。
- 可以多次经过同一个点，但必须走满
n步。 -
n = 0时，不移动算一种走法。 - 答案不需要取模；下方整数接口适用于计数在可表示范围内的输入。
题意分析
圆环上有
10个位置，依次编号为0到9，相邻位置可以双向移动，首尾位置也相邻。从0出发，每次必须向左或向右移动一步，求恰好走n步后回到0的不同走法数量。走法按每一步的方向序列区分，不允许停在原地。中途经过原点仍要继续走满规定步数；绕完整圈回到原点也算，因此不要求向左和向右的次数一定相等。零步不动算一种完成方式。
解法：圆环位置动态规划
核心思路
[!blue]
未来能怎样移动，只取决于已经走了多少步和当前停在哪里，不需要保存整条历史方向序列。令
ways[step][pos]表示恰好走step步后停在pos的走法数。目标就是ways[n][0]，初始只有ways[0][0] = 1，其他位置为零。走完当前一步后要停在
pos，上一步只能位于它的两个邻点之一。左邻点的每条历史路径向右走一步，右邻点的每条历史路径向左走一步，都会到达当前点；两类的最后一步方向不同，互不重复且覆盖全部来源，因此把两个邻点上一轮的方案数相加即可。圆环首尾相接，左邻点下标写成
(pos - 1 + 10) % 10，右邻点写成(pos + 1) % 10。左边先加环长，是为了在pos = 0时也得到非负的合法下标，而不是依赖负数余数去访问数组。每轮只依赖上一轮，可以把步数维度压缩掉：
dp保存已经走完的步数状态，另建next计算再走一步后的全部位置。必须把next的十个位置都计算完，再整体令dp = next；若直接写回dp，相邻位置可能读到本轮新值，混淆不同步数。本题没有给出模数，代码保留精确加法，不擅自对答案取模。当前接口使用固定宽度整数，适用范围是所有中间计数都能由该整数类型表示的输入；若步数范围会超出这一前提，需要按实际要求选择大整数或题目指定的模数。
解题步骤
- 创建长度为
10的零数组dp，令dp[0] = 1，表示零步时位于原点的唯一方案。- 对每一步新建
next，依次枚举圆环的十个位置。- 找到当前位置的左右邻点，把它们在旧
dp中的方案数相加，写入next[pos]。- 本轮全部位置计算结束后，用
next替换dp，进入下一步。- 完成恰好
n轮后返回dp[0]，而不是累计中途经过原点的次数。
代码实现
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)$，每一步固定计算十个位置；若环长作为输入记为
m，则为 $O(nm)$。- 空间复杂度：$O(1)$，同时使用的两轮数组长度都固定为十；环长为
m时为 $O(m)$。
关键点总结
[!green]
- 状态同时包含确切步数和停留位置，才能区分中途返回与最终返回。
- 按最后一步来自哪个邻点分类，得到没有重复或遗漏的计数转移。
- 先完整计算新一轮，再替换旧一轮，避免相邻依赖被原地覆盖。
- 偶数长度圆环每走一步都会改变位置编号的奇偶性，所以奇数步不可能回到编号为零的原点。
易错点总结
[!yellow]
- 左邻点直接用负数取模，Java 和 Go 都可能得到负下标；应先加上环长。
- 原地覆盖旧状态，会让一轮转移读取不同步数的数据。
- 把
dp[0]初始化成零，所有后续状态都会保持为零，无法生成任何路径。- 最后返回
dp[n]，混淆了步数和位置；滚动后下标只表示圆环位置。- 只统计左右步数相同的方案，会遗漏方向净位移为整圈倍数的回原点路径。
- 方案数随步数增长，固定宽度整数必须满足中间计数不溢出的适用前提；没有指定模数时不能随意取模改变答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| LCP 07. 传递信息 | 简单 | 恰好k轮有向图路径计数可复用，本题图是10个点的双向环且终点回到起点。 |
| 1269. 停在原地的方案数 | 困难 | 原题在线性有界数组上可原地停留，本题只能左右移动且首尾相接，邻居和边界规则不同。 |