The previous question was relatively easy, and the following one is more difficult.
Assume that there are N positions in a row, recorded as 1~N, and N must be greater than or equal to 2
At the beginning, the robot is at the M position (M must be one of 1~N)
If the robot comes to position 1, then the next step is to go right to position 2;
If the robot comes to position N, then the next step can only go left to position N-1;
If the robot comes to the middle position, then the next step can go left or right;
It is stipulated that the robot must take K steps, and how many ways are there to finally reach the position P (P is also one of 1~N)
Given four parameters N, M, K, P, returns the method number.
Problem-solving ideas:
1. If the robot is at position 1, it can only move from left to right
2. If the robot is in position N, it can only move from right to left
3. If the robot is in the middle, it can either go right or left
The question now is how many ways to go back, that is, as long as we can reach the destination and the number of steps is enough, we can walk at will.
When encountering this kind of problem, drawing is the best way:
Suppose there are 6 positions in total, start from position 2, walk 5 steps, and reach position 5, how many ways are there in total?
Recursive method
package code03.Dynamic programming_07;
/**
* Suppose there are N positions in a row, recorded as 1~N, N must be greater than or equal to 2
* At the beginning, the robot is at the M position (M must be one of 1~N)
* If the robot comes to position 1, then the next step can only go to the right to position 2;
* If the robot comes to position N, then the next step can only go left to position N-1;
* If the robot comes to the middle position, then the next step can go left or right;
* It is stipulated that the robot must take K steps, and how many ways are there to finally reach the P position (P is also one of 1~N)
* Given four parameters N, M, K, P, returns the number of methods.
*/
public class Robot_02 {
/**
*
* @param mStart M start position
* @param kSteps K steps
* @param nAll N length
* @param pAim P destination position
* @return
*/
public static int way1(int mStart, int kSteps, int nAll, int pAim)
{
return process(mStart, kSteps, nAll, pAim);
}
public static int process ( int mStart, int kSteps, int nAll, int pAim)
{
//The number of steps is 0, unable to walk
if (kSteps == 0) {
return mStart == pAim ? 1 : 0;
}
// only go right
if (mStart == 1) {
return process(mStart + 1, kSteps-1, nAll, pAim);
}
// only go left
if (mStart == nAll) {
return process(nAll-1, kSteps-1, nAll, pAim);
}
//In the middle position, you can go left or right, and you need to count the sum of going left and right
return process(mStart + 1, kSteps-1, nAll, pAim)
+ process( mStart -1, kSteps -1, nAll, pAim);
}
public static void main(String[] args) {
System.out.println(way1(2,5,6,5));
}
}
For the same problem, we can get:
At position 2, with 5 moves remaining, there are 5 moves
At position 3, there are 4 steps left, and there are 4 ways to move
At position 4, there are 3 steps left, and there are 3 ways to move
At position 5, there are 2 steps left, and there are 2 ways to move;
At position 6, there is 1 move left, and there is 1 way to move
There are repeated back and forth moves in the middle, which shows that we have repeated derivation results, so we naturally transition to the recursive + dynamic programming method for optimization.
Recursion + Dynamic Programming
package code03.Dynamic programming_07;
/**
* Suppose there are N positions in a row, recorded as 1~N, N must be greater than or equal to 2
* At the beginning, the robot is at the M position (M must be one of 1~N)
* If the robot comes to position 1, then the next step can only go to the right to position 2;
* If the robot comes to position N, then the next step can only go left to position N-1;
* If the robot comes to the middle position, then the next step can go left or right;
* It is stipulated that the robot must take K steps, and how many ways are there to finally reach the P position (P is also one of 1~N)
* Given four parameters N, M, K, P, returns the number of methods.
*/
public class Robot_02_opt1 {
/**
* @param mStart M start position [0-nAll]
* @param kSteps K steps
* @param nAll N length
* @param pAim P destination position
* @return
*/
public static int way1(int mStart, int kSteps, int nAll, int pAim)
{
/**
* The position is 1-N, each position has a different way of walking, each position is the row, then the range of the row is 1-N
* Since the java array subscript starts from 0, if you want to get the 1-N range, you need to add 1 to the length
*
* We put the remaining steps into columns, so that the remaining steps of each position can be observed intuitively
*/
int[][] dp = new int[nAll + 1][kSteps + 1]; //The number of remaining steps is the abscissa, and the current position is the ordinate
for (int i = 0; i < dp. length; i ++ ) {
for(int j = 0; j <dp[i].length; j ++ ) {
dp[i][j] = -1;
}
}
int result = process(mStart, kSteps, nAll, pAim, dp);
return process(mStart, kSteps, nAll, pAim, dp);
}
public static int process ( int mStart, int kSteps, int nAll, int pAim, int[][] dp)
{
if (dp[mStart][kSteps] != -1) {
return dp[mStart][kSteps];
}
int result;
if (kSteps == 0) {
result = mStart == pAim ? 1 : 0;
}
// only go right
else if (mStart == 1) {
result = process(mStart + 1, kSteps-1, nAll, pAim, dp);
}
// only go left
else if (mStart == nAll) {
result = process(nAll-1, kSteps-1, nAll, pAim, dp);
}
//In the middle position, you can go left or right, and you need to count the sum of going left and right
else {
result = process(mStart + 1, kSteps-1, nAll, pAim, dp)
+ process( mStart -1, kSteps -1, nAll, pAim, dp);
}
dp[mStart][kSteps] = result;
return result;
}
public static void main(String[] args) {
System.out.println(way1(2,5,6,5));
}
}
Pure dynamic programming method
1. According to the recursive method, we know that if the number of remaining steps is 0, then if the starting position is exactly at the target position, it is considered as one way of moving. And it can be deduced that the first column of the two-dimensional array, the fifth row is 1, and the others are 0
if (kSteps == 0) {
return mStart == pAim ? 1 : 0;
}
| x | x | x | x | x | x |
| 0 | |||||
| 0 | |||||
| 0 | |||||
| 0 | |||||
| 1 | |||||
| 0 |
2. According to the recursive method, if you are at the far left end, you can only go right; if you are at the far right end, you can only go left. At present, the first column of data has been deduced. So it needs to be deduced from the first column.
//Can only go to the right
if (mStart == 1) {
return process(mStart + 1, kSteps-1, nAll, pAim);
}
// only go left
if (mStart == nAll) {
return process(nAll-1, kSteps-1, nAll, pAim);
}
According to the recursive code, we know whether it is going left or right.
The second column of the second row, that is, dp[1][1], is the data of the previous column of the next row. The last column of the last row is the data of the previous column of the previous row. Derivation results”
| x | x | x | x | x | x | |
| 0 | 0 | |||||
| 0 | ||||||
| 0 | ||||||
| 0 | ||||||
| 1 | ||||||
| 0 | 1 |
| x | x | x | x | x | x |
| 0 | 0 | ||||
| 0 | 0 | ||||
| 0 | 0 | ||||
| 0 | 1 | ||||
| 1 | 0 | ||||
| 0 | 1 |
By analogy, the final value obtained is:
| Remaining 0 | Remaining 1 | Remaining 2 | Remaining 3 | Remaining 4 | Remaining 5 | |
| Target position 0 | x | x | x | x | x | x |
| target position 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| target position 2 | 0 | 0 | 0 | 1 | 0 | 5 |
| target position 3 | 0 | 0 | 1 | 0 | 4 | 0 |
| target position 4 | 0 | 1 | 0 | 3 | 0 | 9 |
| target position 5 | 1 | 0 | 2 | 0 | 5 | 0 |
| target position 6 | 0 | 1 | 0 | 2 | 0 | 9 |
According to the topic, we know that the position is from 1 to N, that is to say, there is no position of 0. And the position of our table is used as a row, and the remaining steps are used as a column. Therefore, a position of 0 is ignored directly.
Suppose there are 6 positions in total, start from position 2, walk 5 steps, and reach position 5, how many ways are there in total?
dp[2][5] can get a result of 5, that is, 5 kinds of moves.
package code03.Dynamic programming_07;
/**
* Suppose there are N positions in a row, recorded as 1~N, N must be greater than or equal to 2
* At the beginning, the robot is at the M position (M must be one of 1~N)
* If the robot comes to position 1, then the next step can only go to the right to position 2;
* If the robot comes to position N, then the next step can only go left to position N-1;
* If the robot comes to the middle position, then the next step can go left or right;
* It is stipulated that the robot must take K steps, and how many ways are there to finally reach the P position (P is also one of 1~N)
* Given four parameters N, M, K, P, returns the number of methods.
*/
public class Robot_02_opt2 {
/**
*
* @param mStart M start position
* @param kSteps K steps
* @param nAll N length
* @param pAim P destination position
* @return
*/
public static int way(int nAll, int mStart, int pAim, int kSteps)
{
if (nAll < 2 || mStart < 1 || mStart > nAll || pAim < 1 || pAim > nAll || kSteps < 1) {
return -1;
}
/**
* The position is 1-N, each position has a different way of walking, each position is the row, then the range of the row is 1-N
* Since the java array subscript starts from 0, if you want to get the 1-N range, you need to add 1 to the length
*
* We put the remaining steps as a column, so that the remaining steps of each position can be observed intuitively.
* Similarly, the length of the column also needs to be increased by 1.
*
* In fact, it doesn't matter what is listed here, even if it is 100. But if it is 100, it will deduce that
* In the case of going 100, there is no need to waste resources. The best way is based on the actual business, you want me to deduce
* A few steps, I will deduce a few steps to save resources
*/
int[][] dp = new int[nAll + 1][kSteps + 1];
//The number of remaining steps is 0, deduce which behavior corresponds to 1
dp[pAim][0] = 1;
//According to the remaining steps, deduce the result that each position can reach the target position
for (int col = 1; col <= kSteps; col ++ )
{
//Each column value in row 2 corresponds to the previous column value in row 3
dp[1][col] = dp[2][col-1];
//Start from the second line and end after the penultimate line is executed
for (int row = 2; row < nAll; row ++ )
{
//The middle row is equal to the sum of the previous column of the previous row and the next row
dp[row][col] = dp[row-1][col-1] + dp[row+1][col-1];
}
//The last row, each column value corresponds to the value of the previous column of the previous row
dp[nAll][col] = dp[nAll-1][col-1];
}
//According to the current position, the number of remaining steps. Different ways to get to the target position
return dp[mStart][kSteps];
}
public static void main(String[] args) {
System.out.println(way(6,2,5,5));
}
}