javaalgorithmdata-structuresdynamic-programming

# Wrong output with dynamic programming on Limited Subway Surfer challenge

I tried solving this code challenge using Dynamic Programming, but I do not get expected result.

## The "Limited Subway Surfer" challenge

Nidhi has created an alternate version of Subway Surfer game. Her new version is not on a train track unlimited length, rather limited to a track of length N + 1. Just like the original game, this alternate version also has three lanes.

The track has points on it ranging from 0 to N.

In the three lanes, at some points, certain manholes are present. Now, to avoid these manholes, our player needs to jump sideways and switch lanes, as he cannot go from i to (i + 1)th point on the same lane if there is no manhole on the lane at point i + 1.

You are given an array manholes of length N + 1 where `manholes[i]` tells us on which lane is the manhole present for point i. For example, if `manholes[2]` = 1, this means that on point 2 of the train track, a manhole is present on lane 1.

Find the minimum number of lane changes our player has to perform in order to reach from point 0 to point N on the train track.

### Note:

If `manholes[i]` = 0, this means that for point i, there is no manhole present on any lane.

`manholes[0]` and `manholes[N]` are always 0.

### Input Format:

First line of input contains integer T, representing the number of test cases.

First line of each test case contains the integer N.

Second line of each test case contains N + 1 space separated integers, representing manholes[i].

Our player always begins from the middle lane.

### Constraints:

• `manholes.length == n + 1`
• `1 <= t <= 100`
• `1 <= N <= 5 * 10``4`
• `0 <= manholes[i] <= 3`
• `manholes[0] == manholes[n] == 0`

### Output Format:

Minimum number of lane changes to reach from point 0 to N.

### Sample Input:

``````4
0 1 2 3 0
``````

### Sample Output:

``````2
``````

### Explanation:

The optimal path followed by our player is shown in the image below:

It is clear that to reach from point 0 till point N optimally, our player will have to change lanes twice at minimum.

## Attempt

My code for the above challenge is:

``````    public int minLaneChanges(int[] manholes) {
int N = manholes.length - 1;
int[][] dp = new int[N + 1][3];

// Set initial values
dp[0][0] = dp[0][2] = 0;

// Iterate over the points
for (int i = 1; i <= N; i++) {
// Iterate over the lanes
for (int j = 0; j < 3; j++) {
if (manholes[i] == 0 || manholes[i] == j + 1) {
// Manhole on a different lane, find minimum lane change
dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + 1);
} else {
dp[i][j] = Integer.MAX_VALUE;
}
}
}

return Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2]));

}
``````

My approach is to start in the first row, then I iterate each row and column from second row. If I see a hurdle/Manhole I set the current position value to Max value, else I set the current value to min(previous position on same lane, min(previous of other lanes)+1).

Finally I return min among the last row.

My approach fails. For the example input above, it outputs -2147483648. What is the mistake?

Solution

• Here are some of the issues:

• There is this important specification for the challenge:

Our player always begins from the middle lane.

This already means that your initialisation of `dp` is wrong. The cost to get in the left lane is 1 (one side step). So the initialisation should be:

``````dp[0][0] = dp[0][2] = 1;
dp[0][1] = 0;
``````
• `manholes[i] == j + 1` checks the opposite from what you write in comments just below it. This condition is true when lane `j` has a manhole, so in that case you should execute the `else` block.

• In the `if` block you add 1 to the second argument of the outer `Math.min` call. Combined with the fact that you store `Integer.MAX_VALUE` in some `dp` entries, you risk adding 1 to that value, which evaluates to `Integer.MIN_VALUE` and obviously distorts your results. This is why you got -2147483648 as output in one of your tests. I'd suggest not using `Integer.MAX_VALUE`, but just `N`. That is a large enough value.

• Your code assumes that a lane switch is possible (in the previous row) even when `dp[i-1][j]` has a manhole.

Not a problem, but you can reduce the `dp` array to just one dimension (with three entries). You can incrementally update the same triplet to align it to the current point.

Here is the suggested updated code:

``````    public int minLaneChanges(int[] manholes) {
int N = manholes.length - 1;
int[] dp = new int[]{1, 0, 1}; // Initialise that player is in middle

// Iterate over the points
for (int i = 1; i <= N; i++) {
// If there is a manhole, invalidate paths that arrive there:
if (manholes[i] > 0) dp[manholes[i] - 1] = N;