1981 words - 8 pages

Dynamic Programming (DP) is a problem solving technique that entails breaking down a problem

into easier, simpler subproblems of a similar structure. By storing the optimal solutions to each

subproblem and reusing them as needed, the runtime for a recursively defined solution can be

reduced drastically.

1 Introduction

A classic example of a problem which can be solved using dynamic programming is the task of

computing the nth Fibonacci number. The Fibonacci numbers are defined by Fn = Fn−1 + Fn−2

and F1 = F2 = 1. A na¨ıve recursive approach might attempt to simply define a base case and a

recurrence relation, computing the desired result in O(2N ) time. However, a DP approach reduces

this runtime to a much more favorable O(N). This can be done in one of two ways: top-down

or bottom-up. The top-down approach to DP is very similar to recursion. The same structure

of base case and recurrence is used; however, we store the values we calculate, essentially turning

them into additional base cases. This technique, known as memoization, eliminates unnecessary

recomputation of results. Conversely, the bottom-up approach begins with the first two values,

and builds up to the final result using the recurrence. Generally most of the work involved in a

DP solution is formulating the subproblems and recurrence relations. Once you’re sure that your

solution is correct, the actual implementation is usually quite simple compared to other types of

algorithms. For the rest of this lecture we will describe the various types of DP problems that

appear on USACO contests, and provide a few practice problems for each type. When it comes to

USACO problems, DP is one of the most useful techniques you can learn. You can pretty much

expect at least one DP problem on every Silver and Gold contest.

2 Categories

Dynamic programming problems in computing contests tend to fall into a couple of different cate-

gories. This is by no means intended to be an exhaustive list, but this should be a helpful reference.

Recognizing problems as knapsack-like or interval/tree based can lead to a solution more quickly,

and thinking about how to deal with the base cases in each of these types is an instructive exercise.

2.1 Knapsack

The general integer knapsack problem goes like this: given a knapsack of a particular capacity and

objects each of which have a size and a value, find the set of objects which maximizes the total

value but whose total size is constrained to fit within the knapsack. Some knapsack problems will

allow you to take an unlimited number of each type of object; others will only allow a limited

number of objects. Our solution to this problem is to do dynamic programming on the maximum

value that a knapsack of each size can have in it. Suppose we have a table of the maximum value

that a knapsack of any size can have in it called dp[1..N]. To consider adding another item of size

S, iterate over the dp array and see if placing the current object into the knapsack of size i...

Need help finding an example assignment?