解题思路（动态规划方法）

  • 定义状态： 用 dp[i][j] 表示从 0 点出发，经过 i 步到达点 j 的方案数。
  • 状态转移方程： 每一步可以从当前点顺时针或逆时针移动，因此： dp[i][j] = dp[i-1][(j-1+N)%N] + dp[i-1][(j+1)%N] 这里 (j-1+N)%N 和 (j+1)%N 确保了圆环上的循环关系，防止i-1或i+1可能会超过圆环0~9的范围.
  • 初始条件： dp[0][0] = 1，表示从起点出发，走 0 步仍在起点的方案数为 1。
  • 最终结果： 返回 dp[n][0]，即经过 n 步回到起点的方案数。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
    def circle(self, n: int) -> int:
        # write code here
        N, MOD = 10, 10**9+7#圆环上点的个数，对答案取模数
        dp = [[0] * N for _ in range(n + 1)]#动态规划数组，表示走i步到j的方案数
        dp[0][0] = 1#初始化走0步到0的方法只有一种
        for i in range(1, n + 1):#走i步到j的方案，等于走i-1步到j-1和j+1的方案和
            for j in range(N):#注意有效下标，防止超出
                dp[i][j] = dp[i - 1][(j - 1 + N) % N] + dp[i - 1][(j + 1) % N]
        return dp[n][0]%MOD#走n步到0的方案数，取模