Dynamic Programming | Learn for Master
  • Longest Increasing Subsequence


    The algorithms to find the longest increasing subsequence in a sequence are discussed in various places (including Wikipedia), but in my opinion their exposition is not intuitive.




    M[j] — stores the index k of the smallest value X[k] such that there is an increasing subsequence of length j ending at X[k] on the range ki.


    Precise and succinct but not easy to parse and grasp.

    [Read More...]
  • Longest Common Subsequence

    A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. It is a set of characters that appear in left-to-right order, but not necessarily consecutively.

    Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences.

    Problem definition of Longest Common Subsequence

    1. Given the first sequence which contains (m) symbols X = (x1, x2, x3, …, xm)
    2. Given the second sequence which contains (n) symbols Y = (y1,
    [Read More...]