补充题2. 圆环回原点问题（Circle Return Origin）
频次 ★★★★ · 难度 🟡 · 高频：字节
题目
圆环上有 n 个点（编号 0 ~ n-1），从原点 0 出发，每次可以顺时针走一步或逆时针走一步。给定步数 k，求回到原点 0 的方案数。
示例：
输入: n = 3, k = 2
输出: 2
解释: 0→1→0、0→2→0 两种
思路
二维 DP：dp[i][j] 表示走 i 步到达 j 点的方案数。
转移：dp[i][j] = dp[i-1][(j-1+n)%n] + dp[i-1][(j+1)%n]
起点 dp[0][0] = 1，答案是 dp[k][0]。
滚动数组优化空间：只保留两行。
代码
public int circleReturn(int n, int k) {
int[][] dp = new int[k + 1][n];
dp[0][0] = 1;
for (int i = 1; i <= k; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = dp[i - 1][(j - 1 + n) % n]
+ dp[i - 1][(j + 1) % n];
}
}
return dp[k][0];
}空间优化版（滚动数组）：
public int circleReturn(int n, int k) {
int[] dp = new int[n];
dp[0] = 1;
for (int i = 0; i < k; i++) {
int[] next = new int[n];
for (int j = 0; j < n; j++) {
next[j] = dp[(j - 1 + n) % n] + dp[(j + 1) % n];
}
dp = next;
}
return dp[0];
}复杂度
- 时间：O(k × n)
- 空间：O(n)（滚动数组）或 O(k × n)
边界条件
- k = 0：已经在原点，只有 1 种方案（不走）
- n = 1：只有 1 个点，走任何步都在原点，方案数 = 2
- n = 2：两个点相对，走奇数步不可能回到原点
变式
- 如果每步可走 m 种距离：内层加一层循环枚举所有步长
- 70. 爬楼梯：一维版本
- 二维平面网格回原点：从 (0,0) 出发上下左右走 k 步回原点的方案数，状态升为三维
易错点
- 取模方向：
(j - 1 + n) % n不要漏掉+ n，Java 里-1 % n会是负数 - 步数维度在外层：必须外层循环步数，内层循环点，因为每步的状态依赖上一步
- 滚动数组时 dp[j] 含义是上一步的 j：新行算完前不要覆盖旧行
面试追问
- n = 3, k 很大的时候怎么优化？ 递推是线性的，可以用矩阵快速幂将 O(k) 优化到 O(n³ log k)，但面试中写 DP 即可
- 和「机器人走方格」的区别？ 本题是一维环状封闭道路，62 题是二维开放网格，本质都是计数 DP，区别在状态维度和边界条件