NC--311.圆环回原点

NC311 圆环回原点

圆环上有 10 个点，编号 0~9 。从 0 出发，每次可以顺时针或逆时针走一格，请问一共走且仅走 n 步回到原点的方法有多少种。

数据范围： 1≤n≤104 1≤n≤104 ，由于答案可能会非常大，所以请对答案对 109+7 109+7 取模

---

一开始真没想出来是动态规划，这里需要用二维数组来进行状态转移，我们知道，走N步到第X个点的方法数 = 走N - 1步到第X + 1与第X - 1个点的和，我们可以利用这一点来进行状态转移，而初始状态呢？

很显然，走0步到第0个点的方法只有一种，所以f[0][0] = 0

func circle( n int ) int {
    f := make([][]int, n + 1)
    mod := 1000000007
    for i := 0; i <= n; i ++ {
        f[i] = make([]int, 10)
    }
    f[0][0] = 1
    for i := 1; i <= n; i ++ {
        for j := 0; j <= 9; j ++ {
            f[i][j] = f[i - 1][(j + 1 + 10) % 10]%mod + f[i - 1][(j - 1 + 10) % 10]%mod
        }
    }
    return f[n][0]%mod
}