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\ge 2$.

$$LIS(i,j)=\{\begin{array}{ll}0& \text{if }j>n\\ LIS(i,j+1)& \text{if }j\le n\text{ and }A[i]\ge A[j]\\ max\{LIS(i,j+1),1+LIS(j,j+1)\}& \text{ otherwise}\end{array}$$

Algorithm 1 Longest Increasing Subsequence

procedure LIS($A[1\cdots n]$)

$A\left[0\right]\leftarrow -\infty$

for $i\leftarrow 0$ to $n$ do

LIS$[i,n+1]\leftarrow 0$

end for

for $j\leftarrow n$ down to $1$ do

for $i\leftarrow j-1$ down to $0$ do

if $A\left[i\right]\ge A\left[j\right]$ then

LIS$[i,j]\leftarrow$ LIS$[i,j+1]$

else

LIS$[i,j]\leftarrow max\left\{LIS\right[i,j+1],1+LIS[j,j+1\left]\right\}$

end if

end for

end for

return LIS$[0,1]$

end procedure