编程知识 cdmana.com

Algorithmic problem - cycle steps

/**
 *  author : Dreamy patients 
 *  link :https://www.nowcoder.com/discuss/582954?channel=666&source_id=feed_index_nctrack
 *  source : Cattle from 
 *
 *  There is... On a ring 0,1,2,3,4,5,6,7,8,9  total 10 Nodes , A pointer starts at 0 node , Only one step at a time , You can go clockwise or counterclockwise , Excuse me, I'm leaving n Then go back to 0 node , How many different ways are there ?
 *  for example n=1, The path is (0,1),(0,9), Output 0
 * n=2, The path is (0,1,2)(0,1,0)(0,9,0)(0,9,8)  Output 2
 * @param n
 * @return
 */

The simplest way to solve this problem is recursion .

int res = 0;
public int fun(int n){
    dfs(0,n);
    return res;
}
/**
 * * @param i: Current index 
 * @param n: There are a few steps left 
 */
private void dfs(int i, int n) {
    // It's over 
 if (n == 0){
        // Is it back to 0 spot 
 if (i == 0){
            // Add one to the total number of methods 
 res++;
        }
        return;
    }
    // Clockwise 
 int nextL = (i + 1) % 10;
    dfs(nextL,n-1);
    // Anti-clockwise 
 int nextR = (i - 1) % 10;
    dfs(nextR,n-1);
}

But obviously it can be optimized , It's dynamic programming .
We use a two-dimensional array matrix To record the number of methods .
martrixi There is still i Step by step , The current position is j, Yes martrixi There are two ways to get to 0 spot .
We from 1 Step by step , Count to n Step , Last matrixn It means that the current position is 0, And then there were n Step , Yes matrixn One way to get to 0 spot , therefore matrixn That's the answer we need .

public int dp(int n){
    //matrix[i][j] It means that there are still i Step by step , The current position is j, There can be matrix[i][j] One way to get to 0 spot 
 int[][] matrix = new int[n+1][10];
    // only 0 Step by step , There can only be 0 Methods ( In fact, it is not necessary to write , It's easy to understand )
 for (int i = 0;i < 10;i++) {
        matrix[0][i] = 0;
    }
    // initialization , When there's only one step left ,1,9 There's a way to get there 0 spot , All the other places are 0 Methods 
 matrix[1][1] = 1;
    matrix[1][9] = 1;
    //i How many steps are left , from 2 Step by step 
 for (int i =2;i < n+1;i++) {
        //j Indicates the current location 
 for (int j = 0;j < 10;j++) {
            if(j>0&&j<9)
                // arrive 0 The number of point methods is equal to the sum of the two positions in the previous step (j-1 and j+1 On behalf of Shun / The position of the previous step of the counter clockwise )
 matrix[i][j] = matrix[i - 1][j + 1] + matrix[i - 1][j - 1];
            if(j==0) // This is also the sum of the two positions in the previous step , But the position minus a little bit is less than 0, So just use 9 The position of the first step is counter clockwise 
 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://cdmana.com/2020/12/20201225122641863y.html

Scroll to Top