编程知识 cdmana.com

Algorithmic problem - cycle steps

/**
*  author ： Dreamy patients
*  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];
// 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[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;
matrix = 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];
if (j == 9)
matrix[i][j] = matrix[i - 1] + matrix[i - 1][j-1];
}
}
return matrix[n];
}

https://cdmana.com/2020/12/20201225122641863y.html

Scroll to Top