1、前言

题目描述：圆环上有 n 个点，编号为0 ~ n-1。从0点出发，每次可以逆时针和顺时针走一步，问走 step 步回到0点共有多少种走法。

输入：n = 10，step = 2（表示10个环，走2步）

输出：2

2、思路

首先这是个环，所以往右走很方便，直接 (i + 1) % n 即可。但是对于往回走的话，比如从0减1，就得-1了，显然不符合要求，本来应该是12。那么我们可以采用 ((i - 1) + n) % n 的思路来，针对-1，直接就是12；针对正数，直接就是原来的数 + 0，还是原来的数。

对于代码，可以用记忆法来加快速度，这里只是提供一个思路。

3、代码

public class QC_BackToZero {

    public int backToZero2(int n, int step){
        int[][] dp = new int[step + 1][n];

        dp[0][0] = 1;
        for(int i = 1; i <= step; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = dp[i - 1][(j + 1) % n] + dp[i - 1][(j - 1 + n) % n];
            }
        }

        return dp[step][0];
    }



    public int backToZero(int n, int step){
        return dfs(n, 0, step);
    }

    private int dfs(int n, int i, int step) {
        if(step == 0){
            if(i == 0){
                return 1;
            }else {
                return 0;
            }
        }

        int one = dfs(n, (i + 1) % n, step - 1);
        int two = dfs(n, ((i - 1) + n) % n, step - 1);

        return one + two;
    }


    public static void main(String[] args) {
        System.out.println(new QC_BackToZero().backToZero2(13, 16));
    }
}