圆环回原点

圆环回原点的状态如何定义？

• 问题: 圆环上有 10 个点编号 0~9, 从 0 出发每次可顺时针或逆时针走一步, 求走 n 步回到 0 的走法数量;
• 阶段: 按已走步数划分;
• 状态: dp[step][index] 为走 step 步后到达位置 index 的走法数量;
• 特点: 输入没有显式的数组或矩阵, 阶数由问题变量自行构造, 属于无串线性 dp;

转移方程如何写？

• 来源: 位置 index 只能由 index-1 顺时针到达, 或由 index+1 逆时针到达;
• 环形处理: 用取模把 -1 和 10 折回环上;
• 方程: dp[step][index] = dp[step-1][(index-1+len)%len] + dp[step-1][(index+1)%len];
• 初值: dp[0][0] = 1, 其余为 0;
• 答案: dp[n][0];
• 复杂度: 时间 O(n * len), 空间 O(n * len);

class Solution:
    def backToOrigin(self, n):
        length = 10
        dp = [[0] * length for _ in range(n + 1)]
        dp[0][0] = 1
        for step in range(1, n + 1):
            for index in range(length):
                dp[step][index] = (
                    dp[step - 1][(index - 1 + length) % length]
                    + dp[step - 1][(index + 1) % length]
                )
        return dp[n][0]

为什么环形要用取模而不是特判两端？

• 等价性: 取模把 -1 映射到 len-1, 把 len 映射到 0, 与手写 if 分支效果一致;
• 好处: 转移方程保持统一, 减少边界分支导致的错误;

空间可以怎样优化？

• 观察: 第 step 层只依赖第 step-1 层;
• 做法: 用两个长度为 len 的数组滚动, 或原地更新时先用临时数组保存上一层;
• 注意: 环形转移同行内相互依赖, 不能像 不同路径 那样直接原地覆盖;