Dynamic Programming

A good percentage of the problems on UVA can be solved using dynamic programming (DP for short) so being familiar with the various ways to solve such problems is important.

Solving more of such problems is the best way to get better at it. Eventually you'll notice some pattern of similarity in DP problems, typically some kind of optimization or combinatorics problem which can be formulated in a recursive fashion.

Another approach to thinking about DP problems is given by Prof Kirk Pruhs at http://www.cs.pitt.edu/~kirk/papers/dynprog.ps

Using a DP algorithm involves modelling the problem in terms of a recurrence relation of an objective function

Usually there are several ways to formulate the given problem statement for DP, it is worthwhile to do a quick analysis of the complexity of the method you intend to use before actually coding it out. The complexity of a DP algorithm is roughly number of entries in the DP table x time taken to compute an entry.

If the given parameter n at most 2000, an O(n²) DP method might make it in time but an O(n³) algorithm will most likely get time limit exceeded (TLE) unless you are certain that the worst case never happens.

Some common approaches to reduce the time complexity are:

• Look for an alternative formulation that has a lower complexity. Perhaps we need to use two DP tables instead of only one.

• Are all the variables in your formulation absolutely necessary ? is it possible to represent some of the variables as a function of other variables or by using some global variables?

• Do we really need to compute the whole table bottom up or can we just compute the values which are needed to solve a particular instance using memoization ?

Another problem that can arise is when your DP consists of too many variables (normally known as the curse of dimensionality) and you need an extremely large array to hold all the computed values and this leads to memory limit exceeded (MLE) on the online judge

Some common approaches to reduce the memory needed are:

• Do we need all the previous values of the DP table when we compute the current value ? Most of the time we only need the value which are “close” to the current one, for example when computer the nth line of the pascal's triangle we only need the n-1 th line and not the whole triangle. This suggest that we can use two arrays, one for the values in the previous row and one for the values we are computing in the current row.

• Sometimes we cannot apply the first point because there is no fix pattern to the previous values needed to computer the current value, however if we do not need to compute all the entries maybe we can use a hash table to index and store those entries which we need to compute

• If we only exceed the memory limit (usually 32MB) by a little, maybe we can use a less precise data type for each element in the table, using a char instead of int (in C/C++) reduced the memory needed to one quarter of the original

• Sometimes we really need to compute the whole table but maybe we can trade time for space, we do not store all the computed values since that requires too much memory so perhaps we store half of the computed values (assuming that it fits in memory) then if we wish to retrieve values that are not stored we simply compute it again

• Dynamic programming notes (from various online sources)