# Dynamic Programming: Examples

Bart Massey

## Pseudocode and Midterm 2

Given: Array a of n positive integers

Find: Rearrangement of a such that

All odd numbers are in increasing order

All even numbers are in increasing order

Every pair of even numbers of the form n, n + 2 is separated by an odd number

Fail otherwise

Part A: Find an O(n

^{2}) time O(1) space algorithmStrategy: Use modified selection sort to put consecutive elements in place; try to place the even elements first, subject to the constraints

`for i in 0..n-1 j <- index of the minimum even element in a[i]..a[n-1] if j exists and (i = 0 or a[i-1] =/= a[j] - 2) swap a[i] with a[j] continue j <- index of the minimum odd element in a[i]..a[n-1] if j exists swap a[i] with a[j] continue fail`

Part B: Find an O(n lg n) time O(n) space algorithm

Strategy: Sort the evens and odds separately, then take from them one at a time in the right order.

`a_odd <- copy of odd elements of a a_even <- copy of even elements of a sort a_odd and a_even for i in 0..n-1 if a_even is nonempty candidate <- first element in a_even if (i = 0 or a[i - 1] =/= candidate - 2) a[i] <- candidate delete candidate from a_even continue if a_odd is nonempty a[i] <- first element in a_even delete first element from a_even continue fail`

## Longest Increasing Subsequence

Sequence: A sequence s can be thought of as a function from index to element, which can in turn be thought of as a set of tuples.

`s = [5, 9, 7, 4] {(0, 5), (1, 9), (2, 7), (3, 4)}`

Subsequence: A subsequence t of s is a subset of the map of s, with the indices compressed to be sequential.

`t = {(0, 9), (1, 4)} [9, 4]`

Given: Sequence s of integers

Find: Longest subsequence t of s such that for all i in 1..|t|-1 we have t[i-1] < t[i]

Strategy: Recursion / induction on prefix of s. Specifically, find the LIS ending at s[i] by finding an LIS of s[0]..s[i-1] that ends with a number smaller than s[i]

Dynamic programming reduces complexity to O(n

^{2}) time O(n) spaceO(n lg n) algorithm is https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

The basic idea is to keep track of a bunch of sequences sequences, and binary search on the current value to figure out which can be extended and which must be dropped.

## Integer Partition

Given: Sequence s of positive integers. Partition count k.

Find: Splitpoints p[1]..p[k-1] minimizing

`max[i=1..k] sum(s[p[i-1]]..s[p[i] - 1])`

where p[0] = 0, p[k] = |s| + 1

Strategy: For each possible first partition, find the best remaining k-1 partitions and their maximum sum.

Dynamic Programming: Remember the partition values and sums for each starting point and each k

## Other Problems from Skiena

Morphing

Parsing

Triangulation

Unification

Bar Codes

## Optimality Principle

Partial solution can be extended in some pre-determined order

Extension is function only of some metric of previous partial solutions