add some notes on dynamic programming

1 files changed, 53 insertions, 0 deletions

diff --git a/notes.md b/notes.md
index db9c506..7598d56 100644
--- a/notes.md
+++ b/notes.md
@@ -1469,3 +1469,56 @@ f(n) =  n
 | tight bound | theta |
 
 Useful when you cannot get the exact polynomial for a function.
+
+## Dynamic Programming
+
+Dynamic Programming means tabular programming or Dynamic Planning. This term was
+created before coding style programming was a thing.
+
+This is a design technique used to solve a class of problems.
+
+Example: Longest Common Subsequence (LCS)
+
+Important in computation biology like finding commonalities in two DNA strings.
+
+Given two sequences `x[1...m]` and `y[1..n]`, find *a* longest sequence common to
+both. "a", not "the" LCS.
+
+
+```plaintext
+x: A B C B D A B  | BDB
+y: B D C A B A    | BAB
+                  | BDAB
+                  | BCAB
+                  | BCBA
+                  = LCS(x, y)
+                   * functional notation but not a function it's a relation.
+                   * classic misuse of notation
+```
+
+Brute force algorithm for solving this algorithm.
+  * check every subsequence of x from 1..m (`x[1..m]`) to see if it's also a subsequence of `y[i..n]`
+  * analysis check:
+    * Q: How long does it take me to see if it's a subsequence of y?
+    * A: The length of y which is `O(n)`.
+    * Check = `O(n)`
+    * Q: How many subsequences of `x` are there?
+    * A: 2^m subsequences of `x`
+    * running time: `O(n*2^m)` (exponential time = slow!)
+
+Simplification:
+
+1. Look at length of `LCS(y, y)`.
+2. Extend the algorithm to find LCS itself.
+
+Notation: `|s|` denotes length of seq s.
+
+
+15.1 Dynamic Programming
+
+Dynamic Programming, like the divide and conquer method, solves problems by
+combining solutions to subproblems.
+
+Divide and conquer algorithms partition the problem into disjoint subproblems,
+solve the subproblems recursively, and then combine their solutions to solve the
+original problem.