Introduction
First step to learn again is to play this rename game on stackexchange.com discussion post.
Dynamic Programming should be renamed
Discussion is here.
Dynamic programming
Julia's favorite verse:
Smart recursion plus memoization leading to a faster algorithm.
How to recognize that a problem may admit a smart recursion and come up with it? A common case is divide and conquer.
A
Any recurrence whatsoever
D
defining the subproblems
recursively solving the subproblems
F
frugal bottom-up recursion
I
Inductive Programming
Reverse Inductive Programming
L
Linear programming, integer programming, semidefine programming
Extract a recursive structure from the problem, and write down as a recurrence ( modeling)
"Solve the obtained recurrence in a bottom-up way" (algorithms)
M
Multistage planning
Multiway-Divide and Memoized-Conquer, and Merge all subproblems
Memoiztion
O
Overlapping-divide-and-conquer
R
Reverse Inductive Programming
Recursive view
Recursive horizon
S
Splice-and-combine
To go with divide-and-conquer
Or overlapping-divide-and-conquer
Smart recursion, but not tables "table and fill"
T
Tabular/ tabulated recursion
Tabular call caching
Tables are sometime used.
Dynamic programming over trees (Maximum independent set), it uses a tree, or in some cases a tree of arrays,
or an array of trees, or in some cases a Cartesian product of trees.
Actionable Items
Google some keywords in the following list:
frugal bottom-up recursion
Tabular/ tabulated recursion
Maximum independent set
Overlapping-divide-and-conquerStudy the ICPC coach website: a Utah professor with great performance on Hackerrank.
No comments:
Post a Comment