AvoidRoads - 2003 TCO Semifinals 4 - TopCoder

Dynamic Programming

The problem wants to know in how many ways one can reach destination ( cell[width][height] )

If there were no obstacles, then it was a discrete mathematics problem, but now that we have obstacles in the path we have to calculate it in a dynamic programming approach.

What's the 'state' in this problem? ( 'state' a way to describe a situation, a sub-solution for the problem )

dp[i][j] = ( i > 0 ? dp[i-1][j] : 0, j > 0 ? dp[i][j-1] : 0 )

This recurrent relation is true if there are no obstacles in the path, but now what? Since we can come from two cells to the current cell, we have to check whether it is possible to come from cell[i-1][j] to cell[i][j] or from cell[i][j-1] to cell[i][j], each of which is not possible we assume it zero, OK but how do we determine whether it is possible or not? I build a set of pair

and that tells me that you cannot go from pairONE to pairTWO.