Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
If there isn't any backtracking then what happens when my algorithm can't push a button on the current square (because the +2,+3 and +5 are all red) but a solution still exists? –  Ash Nov 13 '11 at 23:34
    
Then you just move on to the next reachable square. For example, suppose the only red squares are 12, 13 and 15 and you're trying to reach 20. When you're processing 10 you find that you can jump anyway, so you shrug and look at 11 instead. At that time 11 will already have been marked as reachable (in various different ways, because you have already processed 6, 8 and 9), so you mark 14 and 16 as reachable. Next up is 12, which you skip because it is red, and 13 likewise. 14 is white and reachable, so mark 16, 17, 19 ... –  Henning Makholm Nov 13 '11 at 23:46
    
In other words, the dynamic programming algorithm does not actually push buttons during the search phase -- it merely plans how buttons could be pushed if afterwards you decide that you need to reach a specific square. –  Henning Makholm Nov 13 '11 at 23:48
    
I understand now, thank you. –  Ash Nov 13 '11 at 23:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.