I want to come up with a counter example that proves the following greedy algorithm doesn't work and give an alternative correct algorithm. The problem is I have an array of numbers and I want to reach the last element of the array in the minimum number of steps. At each step, I can move to any element with the same value, move forward one, or move backward one. The greedy criterion is to move furthest to the right as much as possible. For example, if we have array {1,2,3,4,1,5}, the algorithm will start at 1 move to 1 before the 5 then moves to 5 with number of steps of 2.
An an example of input instance that proves the given greedy algorithm wrong might be {1,2,1,3,2} where the given algorithm crosses the array in 3 steps whereas there is an optimal solution of moving from 1 to the second 2 right to last 2 in two steps. Now, what is a correct algorithm for solving this problem ?