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

/**
 * 作者：爱做梦的病人
 * 链接：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];
}