Dynamic Programming

Any recursive mathematical formula can be directly translated to a recursive algorithm, but sometimes an inefficient program is the net result (recall our recursive Fibonacci algorithm from day one).

Dynamic programming is a non-recursive approach that records the solutions to sub-problems in a table and it solves each sub-problem exactly once.

Longest Common Subsequence Problem

There area few ways in which two strings can be judged to be “similar”:

If one is a substring of another.

ACCGGTCGAG

CGGTCG

If the number of changes needed to convert one string into the other is “small”.

ACCGGTCGAG

GCTGGTCTAG

(only need to change three characters)

If there are many characters in the same order, but not necessarily consecutive.

ACCGGTCGAG

GCTGGTCTRAG

CGGTCAG is common to both strings.

The last example is known as the longest common subsequence problem.

Given a sequence , a sequence is a subsequence of if there exists a strictly increasing sequence of indices of such that for all , .

Just says that a subsequence is just the given sequence with zero or more elements left out.

is a subsequence of with corresponding index sequence . That is , , , and .

Given sequences and , is a common subsequence of and if is a subsequence of both and .

The longest common subsequence problem finds the maximum length subsequence given and .

A brute force approach enumerates all subsequences of and checks to see if they are subsequences of , keeping track of the current longest subsequences.

Dynamic Programming

Dynamic Programming

Longest Common Subsequence Problem

There area few ways in which two strings can be judged to be “similar”:

If one is a substring of another.

If the number of changes needed to convert one string into the other is “small”.

(only need to change three characters)

If there are many characters in the same order, but not necessarily consecutive.

CGGTCAG is common to both strings.

The last example is known as the longest common subsequence problem.

Given a sequence , a sequence is a subsequence of if there exists a strictly increasing sequence of indices of such that for all , .

Just says that a subsequence is just the given sequence with zero or more elements left out.

is a subsequence of with corresponding index sequence . That is , , , and .

Given sequences and , is a common subsequence of and if is a subsequence of both and .

The longest common subsequence problem finds the maximum length subsequence given and .

A brute force approach enumerates all subsequences of and checks to see if they are subsequences of , keeping track of the current longest subsequences.

How many subsequences of are there?

If contains elements, there are subsequences.

0000 (empty sequence)0001 0010 0011

0100 0101 0110 0111

1000 1001 1010 1011

1100 1101 1110 1111

0 = NOT in subsequence1 = in subsequence

Given a sequence , the prefix of , for is .

Theorem: Optimal substructure of an LCS

Let , and be sequences, and let be any LCS of and .

If , then and is an LCS of and .

If , then implies that is an LCS of and .

If , then implies that is an LCS of and .

The theorem says that the LCS of two sequences contains an LCS of prefixes of the two sequences.

Example: