dp定义

dp[i][j]表示走i步到达编号为j的节点共有多少中方法

状态转移

dp[i][j] = dp[i-1][j-1] (i-1步走到j左边的方法数) + dp[i-1][j+1](i-1步走到j右边的方法数）

注意： 上边为了方便理解，没有处理j-1和j+1的越界问题，在下边代码中体现

base case

注意到状态转移需要上一行的数据，所以需要初始化0行。

dp[0][0] = 1, 其余dp[0][...]初始化为0.

代码

class Solution {
public:
    int circle(int n) { //求走n步回到原点的方法数
        int mod = 1000000007; //结果可能特别大，要对mod取余
        int K = 10;  //圆环上有10个点，编号为[0,9]

        //dp[i][j]表示走i步到点编号为j的点有多少种方法
        vector<vector<int>> dp(n + 1, vector<int>(K));

        //base case
        dp[0][0] = 1;
        for (int j = 1; j < K; ++j) {
            dp[0][j] = 0;
        }


        //状态转移
        //dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
        //因为题目是环，这里用的数组，所以要处理j-1，j+1越界问题
        //故 dp[i][j] = dp[i-1][(j-1+K)%K] + dp[i-1][(j+1)%K]
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < K; ++j) {
                dp[i][j] = (dp[i - 1][(j - 1 + K) % K] + dp[i - 1][(j + 1) % K] ) % mod;
            }
        }

        return dp[n][0];
    }
};