【动态规划】 圆环回原点问题

题目详情

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

输入: 2

输出: 2

解释：有2种方案。分别是0->1->0和0->9->0.

此题同上一题：【动态规划】机器人达到指定位置方法数基本类似，不同之处上面是直线数组上，本题位置是环形数组，由上一题分析得知dp公式：dp[k][i]=dp[k-1][i-1]+dp[k-1][i+1]， 由于本题是环形，i-1和i+1可能走出【0，9】的位置。所以

dp[k][i]=dp[k][i]=dp[k-1][(i-1+N)%N]+dp[k-1][(i+1)%N];

初始条件：dp[0][0]=1;

    public int cirleMoveToOrigin(int K){
        int N=10;
        int[][] dp = new int[K + 1][N];
        dp[0][0] = 1;
        for (int k = 1; k <= K; k++) {
            for(int i=0;i<N;i++){
                dp[k][i]=dp[k-1][(i-1+N)%N]+dp[k-1][(i+1)%N];
            }
        }
        return dp[K][0];
    }

类似题目：

【动态规划】机器人达到指定位置方法数