圆环回原点问题

圆环回原点问题

• 1、从任意点出发，回到原点
• 2、从零点出发

1、从任意点出发，回到原点

10个城市编号0~9，城市之间移动只能前后移动（比如5只能到4或者6），10个城市构成一个环，从0可以到9，从9也可以到0。从任意城市X出发，途径N个城市，问有多少途径回到原点？

public class Main {
    //dp + 递归
    static int solution(int X, int N){
        int result = recur(X, X + 1, N);
        return result * 2;
    }

    static int recur(int X, int Y, int N) {
        if (N == 0) {
            if (Y == X) {
                return 1;
            } else {
                return 0;
            }
        }
        //处理循环
        int pre = Y - 1;
        if (pre < 0) {
            pre = 9;
        }
        int next = Y + 1;
        if (next > 9) {
            next = 0;
        }
        return recur(X, pre, N-1) + recur(X, next, N-1);
    }
    public static void main(String[] args) {
        System.out.println(solution(0, 3));
    }
}

2、从零点出发

圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。

设dp[i][j]为从0点出发走i步到j点的方案数

    public static int backToOrigin( int n) {
        //圆环有多少个元素
        int length = 10;
//        dp[i][j]为从0点出发走i步到j点的方案数
        int[][] dp = new int[length][length];
        dp[0][0] = 1;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < length; j++) {
//                公式之所以取余是因为j-1或j+1可能会超过圆环0~9的范围
                dp[i][j] = dp[i - 1][(j - 1 + length) % length] + dp[i - 1][(j + 1) % length];
            }
        }
        return dp[n][0];
    }