Dynamic Programming

Four steps

Characterize the structure of an optimal solution.
Recursively define the value of an optimal solution.
Compute the value of an optimal solution, typically in a bottom-up fashion.
Construct an optimal solution from computed information

Rod cutting

Imagine you're cutting a rod of length 4 intergerunitcough. You can cut it into various lengths, with different prices:

Length i 1 2 3 4 5 6 7 8 Price Pi 1 5 8 9 10 17 17 20

You can cut this in a number of different ways:

No cut: 1 piece, 4l 1 cut at 1: 2 pieces, 1l and 3l

Algorithm

Given a rod of length n
Assume an optimal solution cuts the rod into k pieces, we use the following notations:
Optimal decomposition:
- n = i1 + i2 + ... + 1k, to maximize profit

Simple case

i=1, r = 1 optimal 1(no cuts)
i=2, r = 5 optimal 1(no cuts)

We maximize our profit by trying all possible ways to cut it, and calculating the maximum

Why isn't this efficient?

If the rod is length n, you have n-1 places to cut. You need to cut or not on each, and you'll need to do each combination.

The run time is going to be 2^(n-1)

Optimal Substructure

An optimimal solution to a problem incorporates optimal solutions to its subproblems, which we can solve independently.

After making a cut, we have two subproblems:

After cutting a rod of length 7 at length 3, we have two subproblems: Optimal length for length three, and optimal solution for length 4.
If you already have the solutions to these subproblems, you can add them and you're done!

Ideally, we want to calculate each of these subproblem's answers once, and then use those answers to derive the following answers

Dynamic programming

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map,etc)

There are two takes on this:

1.) Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.

2.) Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming.

General notes

Dynamic programming is all about optimization - There aren't problems you can mathematically only solve with it, but it makes some much more possible
Used when a divide-and-conquer algorithm is repeatedly solving the same problems, like fibonacci or this division algorithm

Back to the rod

So in our rod's case, we want to cut our rod at each individual point for each spot in our rod. Instead of calculating each subsection, we'll just look up the answer (assuming we're going in increasing order).

Rod of n = 4

Cut 1,3
calculate 1 (can't subdivide, so we know)
calculate cut3(2+1)
- We know 1, so calculate 2
  - We know it's made of 1,1, and we know the price of two. Save the max between the two
- Save max of (2+1, and 3) as 3
Cut 2,2 and we know the max of two.
Cut 3,1, and we know the answer

This cuts down on the brute force significantly, as we short circuit a lot of calculation

Approach

Instead of solving the same subproblems repeatedly, arrange to solve each subproblem just once

let r[0..n] be a new array
r[0] = 0
for j = 1 to n
  q = -infinity
  for i = 1 to j
    q = max(q, p[i] + r[j-1])
  r[j] = q
return r[n]

Running time is Theta(n^2)