Dynamic Programming Algorithm: Walking on Grid

Question

I was given a few practice questions for an upcoming exam. I already have been given the solution for this problem which is described in this picture here

There really is no explanation to the solution.

I am curious as to how I can arrive to an answer here. I figure i can create a bunch of subproblems like

Traversal from A->C, A->D, A->E, then figure out A->B based on the previous solutions. But I am quite lost.

Answer 1

First, how many ways are there to get from (0,0) to (x, y) using only R=right and U=up steps? (No restrictions on not passing through other points.) Each such path with have length x+y and contain x R's and y U's, so there are binom(x+y, x) or binom(x+y, y) ways to do this.

Using this information you could calculate how many paths there are from A-B (call this nAB), from A-C (call it nAC), from A-D, ... etc (all of the combination of pairs). Note that there are no paths from C to D (since you cannot go down) and no paths from D to C since you cannot go left.

Now, use inclusion exclusion. The idea is to subtract off bad cases. For example, a bad case would be starting at A going through C and then to B. How many ways can this be done? nAC x nCB. Another bad case is going through E, there are nAE x nEB ways to do this... subtract them off. Then going through D is also bad. There are nAD x nDB ways to end up at B going through E... subtract those off too. Now, the problem is you've subtracted off too much (paths that go through 2 of the bad points)... so add those back in. How many points go through C and E and end at B? nAC x nCE x nEB, add those in. How many points go through D and E? nAD x nDE x nEB, add those in. In principle, you'd then subtract the paths that went through all three but there are none of those.

Answer 2

This problem can be solved by hand in a way very similar to how you calculate the numbers in Pascal's triangle. In that triangle, every number is the sum of the two numbers above it. Similarly, in your case, the number of ways to get to a certain point (using the shortest path), is simply the sum of the number of ways to get to the point to its left and to the one below it. Demonstrated with ASCII art:

1 -> 1 -> 7 -> 7 ->14
^         ^         ^
|         |         |
1    C    6    E    7
^         ^         ^
|         |         |
1 -> 3 -> 6 -> 6 -> 7
^    ^    ^         ^
|    |    |         |
1 -> 2 -> 3    D    1
^    ^    ^         ^
|    |    |         |
A -> 1 -> 1 -> 1 -> 1

So to calculate the number of paths for a certain field, you first need to know the answer to the two sub-problems to its left and below it. This is a textbook example of a problem that can be solved using dynamic programming. The only tricky bit in implementing this is how you handle the forbidden points and the edges. One way how you could do this in practice would be to initialize all your edges and your forbidden points to zero, and point A to 1:

0 -> 
          ^         ^
          |         |
0 ->      0 ->      0 ->


0 -> 
                    ^
                    |
0 ->                0 ->
     ^
     |
     1 ->
          ^    ^    ^    ^
          |    |    |    |
          0    0    0    0  

From there on, you can calculate all the missing fields using a simple sum, starting from point A in the lower left, and working your way up to point B in the top right:

0 -> 1 -> 1 -> 7 -> 7 ->14
     ^    ^    ^    ^    ^
     |    |    |    |    |
0 -> 1    0 -> 6    0 -> 7
     ^         ^         ^
     |         |         |
0 -> 1 -> 3 -> 6 -> 6 -> 7
     ^    ^    ^    ^    ^
     |    |    |    |    |
0 -> 1 -> 2 -> 3    0 -> 1
     ^    ^    ^         ^
     |    |    |         |
     1 -> 1 -> 1 -> 1 -> 1
          ^    ^    ^    ^
          |    |    |    |
          0    0    0    0