Dynamic programming is a technique for solving problems recursively, with overlapping sub-problems. This approach works only when the solution to sub-problems share the same structure with the final solution. If the prerequisite is satisfied, the conceptual way of solving the problem is to derive the recursion, and builds up the result bottoms-up. Some examples are listed below.

§Knapsack

Problem spec:

Given a set of items, each of which is associated with some weight and value. Find the subset of items which can be carried into the knapsack with weight limit W. It is required that the cumulative value of the items in the knapsack is maximum value possible.

Sample:

For analyzing the problem, let’s focus on the last recursion step, i.e. deciding if last item (weight: 3, value: 50) should be selected. In this case, we only have two options, select it or drop it, corresponding to max value obtained from selecting from the first three items with weight constraint 7, and selecting from the first three items with weight constraint 10.

The complete Java code:

§Hop

Given an array of non-negative integers and a pointer pointing at the zeroth slot of the array. The pointer can only incremented by 4 or 7, and such process repeats until it goes beyond the bound of the array. Devise a moving strategy so that the sum of all slots the pointer pointed reaches the maximum. Your solution should calculate this maximum.

Sample:

The complete Java code:

§Counting change

How many different ways can we make change of \$1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?

The scheme code from http://xuanji.appspot.com/isicp/1-2-procedures.html

My solution using DP in Java. `dp[i][j]` means that using coins up to `coin_kinds[j]`, how many ways there are for exchanging `i` amount of money.