A Collection of Dynamic Programming Problems

This is a collection of interesting algorithm problems written first recursively, then using memoization and finally a bottom-up approach.This allows to well capture the logic of dynamic programming.

Dynamic Programming

The idea behind dynamic programming as describe in The Algorithm Design Manual (S. Skiena):

• Find the recursion in the problem
• Build a table of possible values
• Find the right order to evaluate the results so that partial results are available when needed.

There are two main approaches in the implementation of dynamic programming :

Top Down - Memoization

When the recursion does a lot of unecessary calculation, an easy way to solve this is to cache the results and to check before executing the call if the result is already in the cache.

Bottom-Up

A better way to do this is to get rid of the recursion all-together by evaluating the results in the right order and building the array as we iterate. The partial results are available when needed if the iteration is done in the right order.

We have to identify and initialize the boundary conditions such as when we start the iteration, those are available.

We can most of the time optimize the space and avoid storing all the partial results along the way by storing only the stricly necessary partials.

Collection

For each problem, a simple recursion is presented together with a top down and a bottom-up approach. This allows to have a clear view of the logic of dynamic programming.

The simple recursion is very inefficient obviously and very limited in use, it is there for illustration only.

Fibonnaci

Finding the nth fibonacci number

Input: 4

Output: 3

String Partition

The partition string problem retrieving the original string whose spaces were removed. We are given a list of words belonging to a dictionary

Input: "carlosthinksthattheweatherisnice"

Output: "carlos thinks that the weather is nice"

Counting Paths

Count the number of possible paths from (x1, y1) to (x2, y2) by moving right or down

Input: (0, 0, 1, 1)

Output : 2

Largest Increasing Sequence

Find the largest non-continuous increasing sequence from an array

Input: [1, 6, 7, 4, 6, 1, 3, 4, 6, 19, 12, 14, 35, 66]

Output: [1, 3, 4, 6, 12, 14, 35, 66]

Note that for this problem, the memoization solution is not available since the recursion access each partial solution once.