Introduction To Dynamic Programming: Intermediate

Origin post from Dumitru — a topcoder member

Let’s see now how to tackle bi-dimensional DP problems.

Problem:

A table composed of N x M cells, each having a certain quantity of apples, is given. You start from the upper-left corner. At each step you can go down or right one cell. Find the maximum number of apples you can collect.

This problem is solved in the same way as other DP problems; there is almost no difference.

First of all we have to find a state. The first thing that must be observed is that there are at most 2 ways we can come to a cell – from the left (if it’s not situated on the first column) and from the top (if it’s not situated on the most upper row). Thus to find the best solution for that cell, we have to have already found the best solutions for all of the cells from which we can arrive to the current cell.

From above, a recurrent relation can be easily obtained: S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0) (where i represents the row and j the column of the table , its left-upper corner having coordinates {0,0} ; and A[i][j] being the number of apples situated in cell i,j).

S[i][j] must be calculated by going first from left to right in each row and process the rows from top to bottom, or by going first from top to bottom in each column and process the columns from left to right.

Pseudocode:

For i = 0 to N - 1
    For j = 0 to M - 1
        S[i][j] = A[i][j] +
                max(S[i][j - 1], if j > 0; S[i - 1][j], if i > 0 ; 0)

Output S[n - 1][m - 1

UPPER-INTERMEDIATE

This section will discuss about dealing DP problems which have an additional condition besides the values that must be calculated.

As a good example would serve the following problem:

Given an undirected graph G having positive weights and N vertices. You start with having a sum of M money. For passing through a vertex i, you must pay S[i] money. If you don’t have enough money – you can’t pass through that vertex. Find the shortest path from vertex 1 to vertex N, respecting the above conditions; or state that such path doesn’t exist. If there exist more than one path having the same length, then output the cheapest one. Restrictions: 1<N<=100; 0<=M<=100 ; for each i, 0<=S[i]<=100.

As we can see, this is the same as the classical Dijkstra problem (finding the shortest path between two vertices), with the exception that it has a condition. In the classical Dijkstra problem we would have used a uni-dimensional array Min[i] , which marks the length of the shortest path found to vertex i. However in this problem we should also keep information about the money we have. Thus it would be reasonable to extend the array to something like Min[i][j] , which represents the length of the shortest path found to vertex i, with jmoney being left. In this way the problem is reduced to the original path-finding algorithm. At each step we find the unmarked state (i,j) for which the shortest path was found. We mark it as visited ( not to use it later), and for each of its neighbors we look if the shortest path to it may be improved. If so – then update it. We repeat this step until there will remain no unmarked state to which a path was found. The solution will be represented by Min[N-1][j] having the least value (and the greatest j possible among the states having the same value, i.e. the shortest paths to which has the same length).

Pseudocode:

Set states(i,j) as unvisited for all (i,j)
Set Min[i][j] to Infinity for all (i,j)

Min[0][M]=0

While(TRUE)

    Among all unvisited states(i,j) find the one for which Min[i][j]
    is the smallest. Let this state found be (k,l).

    If there wasn’t found any state (k,l) for which Min[k][l] is
    less than Infinity – exit While loop.

    Mark state(k,l) as visited

    For All Neighbors p of Vertex k.
        If (l-S[p]>=0 AND Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
            Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
    # i.e.
    # If for state(i,j) there are enough money left for
    # going to vertex p (l-S[p] represents the money that
    # will remain after passing to vertex p), and the
    # shortest path found for state(p,l-S[p]) is bigger
    # than [the shortest path found for
    # state(k,l)] + [distance from vertex k to vertex p)],
    # then set the shortest path for state(i,j) to be equal
    # to this sum.
    End For

End While

Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M);
if there are more than one such states:
    then take the one with greater j.
if there are no states(N-1,j) with value less than Infinity:
    then such a path doesn’t exist.