2
$\begingroup$

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.

  1. 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.

  2. 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.

  3. 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 length n. The value of A[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.

1 Answers 1

1

You shouldn't be needing backtracking. The point of dynamic programming is to remember enough about solutions to subproblems that you can later combine them into solutions to larger problems without needing much work.

You just need a one-dimensional table of size $n$, with each cell containing two items of data: (a) the smallest number of moves you know you can reach that cell in, and (b) the index of the previous cell in that sequence. Item (a) is for knowing when you find a better solution. Item (b) allows you to just read out the final solution by following the prev links when you're done.

  • 0
    I understand now, thank you.2011-11-13