圆环回原点问题

问题描述

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

输入： 2
输出： 2
解释：有2种方案，分别是0->1->0和0->9->0

代码实现

public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().backToOrigin(2));
    }

    public int backToOrigin(int n) {
        int length = 10;
        // dp[i][j]为从0点出发走i步到j点的方案数。
        int[][] dp = new int[n + 1][length];
        dp[0][0] = 1;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < length; j++) {
                dp[i][j] = dp[i - 1][(j - 1 + length) % length] + dp[i - 1][(j + 1) % length];
            }
        }
        return dp[n][0];
    }

}