编程知识 cdmana.com

算法题-循环步数

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

版权声明
本文为[kenLoong]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000038651282

Scroll to Top