You don't want to repeat yourself when trying to be efficient. Dynamic programming is the art of keeping track of results you've already computed that are useful in later computations.
seq1
and seq2
.Suppose we are also given a set of operations:
Consider the two sequences below
1 2 

What is the minimum number of operations required to convert one sequence into the other?
Brilli the ant sees a square \(n \times n \) matrix consisting of only \(0\)'s and \(1\)s. He is given the task of finding the largest \(1\) square space( the largest square submatrix consisting of only \(1\)'s) . For example if he was given the below table, the shaded area would be the largest square area:
Unfortunately Brilli is given a matrix of much larger size. Being the competent programmer that he is, he divides the problem into subproblems and comes up with a brilliant dynamic programming solution.
His dynamic programming solution considers the subproblem \(S[i,j]\). \(S[i,j]\) being the side length of the largest \(1\) square space whose bottomright corner is at \(i,j\).
Once he solves the problem, his table has the following values:
\[ S[15][15] = 4 \] \[S[16][14] = 10\] \[S[15][14] = 12 \]
What is the value of \(S[16][15]\)?
The longest common subsequence (LCS) problem is defined as follows:
Given two strings: string \(S\) of length \(n\) and string \(T\) of length \(m\), the goal is to produce their longest common subsequence: the longest sequence of characters that appear lefttoright (but not necessarily in a contiguous block) in both strings.
For example:
\(S\)= BZHAC
\(T\)= HKABFT
Then the longest common subsequence has a length of \(3\) and is HAB
.
Suppose you have the following snippets of two genes which you suspect to code for homologous proteins, but to have diverged long ago on the evolutionary scale. Find their LCS, what is its length?
1 2 3 4 5 6 7 8 9 10 11 12 

Problem Loading...
Note Loading...
Set Loading...