dynamic programming data structure
Table of Contents
- dynamic programming data sturcuture
- Typically, 1D and 2D Array are used. Tree and graph is also possible options.
- tree
- for tree, structural replica of the problem with specific value for each node is a senario.
- Fibonacci number example
- Values of \(T(n)\) are reused, so can memorize used values in an array \(T\) where \(T_n = T(n)\), at each \(T(n)\) is used, check first if it is present in \(T_n\), progress to recursion if it is not.
Backlinks
dynamic programming
dynamic programming is:
- when
- you find the
recurrencereused some value that may require expensive computation - can
- memorize these values with a
dynamic programming data structure. - recurrence
- the recurrence relation on which dynamic programming is useful
usually features multiple occurance of \(T(n+c)\) -like stuff.
- fibonaci number - \(T(n) = T(n-1) +T(n-2)\) -> each number is used twice - 2 occurance of \(T(n+c)\) -like stuff
- (no term)
- dynamic programming data structure
- Working buttom-up or top-down
- working buttom-up(from \(T_0\) to \(T_n\)) or top-down(from \(T_n\) to whatever others that are used) is almost the same in term of computation complexity and algorithm. As writing memorize and fixed-length(or dynamic-length) array with empty value can be difficult in some programming language.
- top-down is more flexible and easy to write in term of logic/equations, if you get the memoize mechnism right
- buttom-up is generally easier to write in code, but as it is translating recursion to loop, it’s trickier and harder to understand.
- with top-down it is natural that you only compute those values that is required. with buttom-up you may calculate some entries that are not used afterwards while enumerating indexes, and have to write extra conditions if you want to optimize that.
- you
needstrong recursion with top-down approach. some programming language don’t have that strong recursion to handle top-down approach, In that case, you have to simulate recursion with loop, which is also tricky.
algorithmic data structure
one or more data structure with additional specification/restriction and/or accompanying algorithm process