Dynamic Programming

We continued our study of dynamic programming with another example.  This one is covered thoroughly in the text so I will not include too much detail here.

In this problem, we have a metal bar which we can cut into smaller pieces.  For each size of piece that we can cut, there is a known (and fixed value).  However, the values for different sizes don't follow any particular pattern - we may even find that a shorter piece is worth more than a longer piece.  Our goal is to cut the bar into a set of smaller pieces with the maximum possible value.

Let Val(i) be the value of a piece of bar i units in length.

Let OptVal(i) be the maximum value we can get from a bar of length i 

We can approach this in two ways:

1.  Consider the cutting operation to be "cut one piece off the end of the bar, then cut up the rest of the bar."  In this approach, the maximum value for a bar of length n is given by this recurrence:

OptVal(n) = max {  Val(1)  + OptVal(n-1)              - what we get by cutting off a piece of length 1, then doing the best we can with the other piece
                               Val(2)  + OptVal(n-2)              - what we get by cutting off a piece of length 2, then doing the best we can with the other piece
                                ....
                               Val(n-1) + OptVal(1)
                               Val(n)                                      - what we get by not cutting the bar at all
                            }

Each line of this formula depends on the solution to a single smaller problem

2.  Consider the cutting operation to be "make the first cut somewhere in the bar, the cut up the two pieces independently of each other".  In this approach, the maximum value for a bar of length n is given by this recurrence:

OptVal(n) = max {    Val(n)                                    - it may be best not to cut the bar at all
                                OptVal(1) + OptVal(n-1)
                                OptVal(2) + OptVal(n-2)
                                OptVal(3) + OptVal(n-3)
                                ...
                                OptVal(n/2) + OptVal(n/2)
                            }

Each line of this formula depends on the solution to two smaller problems.

Whichever approach we take, we see that the same subproblems occur over and over, but there are actually only n-1 different subproblems to solve.  Each one can be solved in O(n) time once the solutions to smaller problems have themselves been found.  The complexity of solving this problem using either recurrence is O(n^2)