关于算法:算法题循环步数

/**
 * 作者：爱做梦的病人
 * 链接：https://www.nowcoder.com/discuss/582954?channel=666&source_id=feed_index_nctrack
 * 起源：牛客网
 *
 * 一个环上有 0,1,2,3,4,5，6,7,8,9 共计 10 个节点，一个指针起始地位在 0 节点，每次只能走一步，能够顺时针走也能够逆时针走，请问走了 n 步之后再回到 0 节点，请问总共有多少种不同的形式？* 例如 n =1, 门路有（0,1），（0,9），输入 0
 * n=2, 门路有（0,1,2）（0,1,0）（0,9,0）（0,9,8）输入 2
 * @param n
 * @return
 */

这道题首先最简略的办法就是递归了。

int res = 0;
public int fun(int n){dfs(0,n);
    return res;
}
/**
 * * @param i: 以后索引
 * @param n：还剩几步
 */
private void dfs(int i, int n) {
    // 走完了
 if (n == 0){
        // 是否回到了 0 点
 if (i == 0){
            // 总办法数加一
 res++;
        }
        return;
    }
    // 顺时针
 int nextL = (i + 1) % 10;
    dfs(nextL,n-1);
    // 逆时针
 int nextR = (i - 1) % 10;
    dfs(nextR,n-1);
}

然而很显著其实还能够优化，就是用动静布局。
咱们用一个二维数组 matrix 来记录办法数。
martrixi 示意在还剩 i 步时，以后地位是 j, 有 martrixi 种办法达到 0 点。
咱们从 1 步开始算，算到 n 步，最初 matrixn 的意思就是以后地位是 0，还剩 n 步，有 matrixn 种办法走到 0 点，所以 matrixn 就是咱们要的答案。

public int dp(int n){//matrix[i][j] 示意在还有 i 步时，以后地位为 j，能够有 matrix[i][j] 种办法走到 0 点
 int[][] matrix = new int[n+1][10];
    // 只剩 0 步时，只能有 0 种办法（这里其实能够不写，写进去是不便了解）for (int i = 0;i < 10;i++) {matrix[0][i] = 0;
    }
    // 初始化，只剩一步时，1,9 地位都有一种办法达到 0 点，其它地位都是 0 种办法
 matrix[1][1] = 1;
    matrix[1][9] = 1;
    // i 示意剩几步，从 2 步开始算
 for (int i =2;i < n+1;i++) {
        // j 示意以后地位
 for (int j = 0;j < 10;j++) {if(j>0&&j<9)
                // 达到 0 点办法数等于前一步的两个地位之和（j- 1 和 j + 1 代表顺 / 逆序时针的前一步地位）matrix[i][j] = matrix[i - 1][j + 1] + matrix[i - 1][j - 1];
            if(j==0) // 这里也是计算前一步的两个地位之和，但地位减一会小于 0，所以间接用 9 代替逆时针的前一步地位
 matrix[i][j] = matrix[i - 1][j + 1] + matrix[i - 1][9];
            if (j == 9)
                matrix[i][j] = matrix[i - 1][0] + matrix[i - 1][j-1];
        }
    }
    return matrix[n][0];
}