Dynamic programming

Nov 22, 2023

When going over the lab7b I wanted to understan more clearly how to identity patterns and similarties to other problems and when to use dynamic programming.

A subsequence of a sequence like a and array, a linked list, or a string, is obtained by removing zero or more elements and keeping the rest in the same sequence order. It is also called a substring if the elements are contiguous in the original sequence.

Working on the examples:

1. Given an array \(A[1...n]\) of integers, compute the length of a longest increasing subsequence of \(A\). A sequence \(B[1...\ell]\) is increasing if \(B[i] > B[i - 1]\) for every index \(i \geq 2\).

\[ LIS(i, j) = \begin{cases} 0 & \text{if } j > n \\ LIS(i, j + 1) & \text{if } j \leq n \text{ and } A[i] \geq A[j] \\ \max \{LIS(i, j + 1), 1 + LIS(j, j+1)\} & \text{ otherwise} \end{cases} \]

    % This quicksort algorithm is extracted from Chapter 7, Introduction to Algorithms (3rd edition)
    \begin{algorithm}
    \caption{Longest Increasing Subsequence}
    \begin{algorithmic}
    \PROCEDURE{LIS}{$A[1 \cdots n]$}
        \STATE $A[0] \gets - \infty$
         \FOR{$i \gets 0$ \TO $n$}
            \STATE LIS$[i, n + 1] \gets 0$
        \ENDFOR
        \FOR{$j \gets n$ down \TO $1$}
            \FOR{$i \gets j - 1$ down \TO $0$}
              \IF{$A[i] \geq A[j]$}
                \STATE LIS$[i, j] \gets$ LIS$[i, j + 1]$
              \ELSE
                \STATE LIS$[i, j] \gets \max \{LIS[i, j+1], 1 + LIS[j, j+1]\}$
              \ENDIF
            \ENDFOR
        \ENDFOR
        \STATE return LIS$[0, 1]$
    \ENDPROCEDURE
    \end{algorithmic}
    \end{algorithm}