A homework question states:
The task is to move a player along a path of n squares starting a square 1 and moving forward each step. At any point you can do one of three things.
Push a blue button moving the player forward 2 squares. If the player has fewer than 2 squares left on the path, then this button terminates the game and the player wins.
Push a yellow button moving the player forward 3 squares. If the player has fewer than 3 squares left on the path, then this button terminates the game and the player wins.
Push a green button moving the player forward 5 squares. If the player has fewer than 5 squares left on the path, then this button terminates the game and the player wins.
Squares are painted either white or red. Square 1 is white. If a player lands on a red square then the player loses the game.
Out input for the algorithm we must provide is an array
A
of lengthn
. The value ofA[i]
tells us whether the i'th square is painted red or white.The output is the smallest number of moves needed to complete the game.
My current (wrong) solution:
I have a table which is k
* n
(where k
is the number of available jumps).
I mark the table cells where the player cannot jump with -
.
I then fill in all the cells the player can jump to providing that the player isn't landing on red squares.
Once the table is filled I try the largest jump first and then backtrack when jumps cannot be made (due to red squares). I then attempt smaller jumps to see if they can be made. If not I move back to where I came from before and attempt smaller jumps until a solution is found. If there is one.
However this feels wrong to me. It appears as though instead of dynamic programming I'm simply using a Bruteforce type Greedy algorithm to solve the problem.