# Dynamic Programming

Dynamic Programming is breaking up problem into series of overlapping sub-problems, and build up solutions to larger and larger sub problems. To know more about Dynamic Programming visit HERE

#### Applications of Dynamic Programming

##### Areas
• Bioinformatics.
• Control Theory.
• Information Theory.
• Operations Research.
• Computer Science: Theory, Graphics, AI, Systems, etc
##### Some Famous Dynamic Programming Algorithms.
• Viterbi for hidden Markov Models.
• Unix diff for comparing two files.
• Smith-Waterman for sequence alignment.
• Bellman-Ford for shortest path routing in networks.
• Cocke-Kasami-Younger for parsing context free grammars.

#### Weighted Interval Scheduling

Job j starts at Sj, finishes at Fj and has weight or value Vj. Two jobs are compatible if they don’t overlap. Find Maximum weight subset of mutually compatible jobs.

• Label jobs by finishing time: f1 <= f2 <= … fn
• p(j) = largest index i < j such that job i is compatible with j.
##### Binary Choice

Notation: OPT(j) = value of optimal solution to the problem consisting of job requests 1, 2, … , j.

Case 1: OPT selects job j. Can’t use incompatible jobs { p(j) + 1, p(j) + 2, … , j -1 }. Must include optimal solution to problem, consisting of remaining compatible jobs 1,2, … , j -1

Case 2: OPT does not select job j. Must include optimal solution to problem consisting of remaining compatible jobs 1,2,…, j-1

#### Brute Force

```Input: n, S1,..., Sn  F1,...Fn  V1,...,Vn

Sort jobs by finish time so that F1 <= F2 <= ... Fn.
compute p(1), p(2), ... , p(n)

Compute-opt(j) {
if (j == 0)
return 0
else
return MAX(Vj + Compute-opt(p(j)), Compute-opt(j-1))
}```