dynamic programming is two things wearing one name. to bellman it was a mathematical theory of multistage decision processes — sibling to linear programming in the “programming means planning” sense.1 𐃏 to a computer scientist it is a technique: solve a problem by combining solutions to subproblems, and never solve the same subproblem twice (Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford, 2009). the two are the same idea at different altitudes, and this page covers both. worked implementations also live in this github repo.
Big-Oh
Complexity Classes
The Computational Zoo is far more subtle and complex than I thought it was.
Computational Zoo
It contains P, NP (+complete), EXP, NP-hard, CO-NP (+complete), PSPACE, BPP, BQP, EXPSPACE, 2-EXP, halting problem, decidable, etc!
Big Oh Notation
Big-Oh ( \(O\) ) gives an upper bound on how an algorithm’s resource consumption grows with input size \(n\).
Backlinks (2)
1. Wiki /wiki/
Knowledge is a paradox. The more one understand, the more one realises the vastness of his ignorance.