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)) }

#### READ MORE

**Algorithms **related posts visit **HERE**

**Data Structures **related posts visit **HERE**

**Databases** related posts Visit **HERE**

**Python-related** posts Visit **HERE**

**C++** related posts Visit **HERE**

**Data Science** related posts visit **HERE**