Dynamic programming

This is an algorithmic technique to solve some recursion type problems in an iterative way. This can speed up this processes dramatically especially when recursion would compute a similar step multiple times.

The basic structure of this technique is to:

1. Break a problem down into smaller sub problems.
2. Use the solutions to previous sub problems to solve subsequent sub-problems.
3. Use the solution to all sub problems to solve the main question.

(If this feels a lot like Induction, that is because this is essentially a programming equivalent.)

Longest increasing subsequence (LIS)

Suppose we are provided with a sequence of numbers and we want to find the length of the longest increasing subsequence in .

This can be done using dynamic programming with the following steps:

Let be the LIS on that ends with .

First note that as there is only 1 term in . Moreover, if for then . Generically though for we need find the longest increasing subsequence that ended with a number before your current term (so ) such that the end number is less than your current term (so ). Mathematically we would say

Then the solution to the LIS problem for a given sequence is , as a longest increasing subsequence has to end with some term.

This requires that the problem has the following properties.

1. Overlapping Subproblems: The problem can be divided into smaller overlapping subproblems that are solved independently.
2. Optimal Substructure: The solution to the problem can be constructed from the optimal solutions of its subproblems.

Advantages

1. Efficiency: Dynamic programming can dramatically reduce the time complexity of algorithms that solve problems with overlapping subproblems.
2. Simplicity: The core idea is often straightforward to implement, making it easier to write correct and efficient code for complex problems.

Limitations

1. Memory: Storing the results of all subproblems can sometimes require a lot of memory.
2. Analytical Complexity: It may be challenging to determine the structure of the subproblems and how to combine them to solve the original problem.

Links

• Lecture notes and worked examples