圆环回原点问题

旧城等待， 2023-10-03 15:25 22阅读 0赞

#### 圆环回原点问题 ####

*  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];
        }