JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook General TopCoder Cookbook Discussion Algorithm dynamic programming recipes
 Algorithm dynamic programming recipes | Reply I plan to write the "Optimizing DP solution" recipe. I've read the article "Dynamic programming: from novice to advanced". It is a good as a DP tutorial but lacks not only time/memory optimizations, but also commonly used state domains (i.e. subsets, vertices of tree, segments, etc) and clear note of difference between forward and backward dynamics (top-down and bottom-up in wikipedia). Will the "Introducing the DP" be similar in this way?The plan for the recipe is now the following:General DP things:1. Difference between forward/backward dynamics.2. How to reconstruct path after DP (store best/recalculate).3. Memoization = lazy DP.Here must be a reference to "Optimizing recurse solutions" and brief words about when and why memoization is better than ordinary DP.Commonly used state domains:4. Multidimensional array, ordered by component-wise <=.Not sure that I should write a lot here since it is the usual DP.5. Subsets, ordered by inclusionHere must be a reference to recipe about iterations over subsets (overall O(3^n) time complexity)6. Substrings of a string, ordered by length.Here Knuth's trick will be described.7. Vertices of tree, ordered by ancestryHere should be a note about time complexity analysis.8. With profiles + broken profiles.General optimizations:9. Parameter dependence in solution spaceEliminating the parameter which is clearly determined from the other parameters.10. Storing fixed number of layers only.Reducing memory of DP if recurrent relations deal with R[i] and R[i+1] only. Also I'm not sure whether I should describe here divide-and-conquer approach for getting the path (don't remember problems that require this trick).11. Precalculation.Quite general words about precalculating values before DP. Binomial coefficients, prefix sums, minimums etc.12. Rotating solution-result problem.It's when state parameter becomes result and result becomes state parameter. Like minimizing size of objects which have overall cost C in Knapsack instead of maximizing overall cost of objects which have size W.13. Not using unnecessary states.Here the simple approaches to accelerate solutions in constant times are described. Like setting tight bounds on loop variables, ignoring states with zero/infinity result since they have no effect.14. Storing possible states in the map.Just mention that it is possible.15. Binary matrix multiplication.Mostly combinatoric problems can be solved with this thing.16. Acceleration with binary search or segment trees or the like.Notes that sometimes complex data structures are necessary. Seldom used in SRMs.And of course "Discussion" will be full of real SRM problems and detailed explanations how to solve them.
 Subject Author Date Algorithm dynamic programming recipes syg96 Dec 25, 2010 at 4:55 AM EST Re: Algorithm dynamic programming recipes Nickolas Dec 25, 2010 at 1:51 PM EST Re: Algorithm dynamic programming recipes syg96 Dec 26, 2010 at 3:11 AM EST Re: Algorithm dynamic programming recipes hacker007 Jan 12, 2011 at 10:45 AM EST Re: Algorithm dynamic programming recipes [torayeff] Oct 29, 2012 at 11:02 AM EDT Re: Algorithm dynamic programming recipes LifeMaker Jan 4, 2013 at 1:47 AM EST
 Forums TopCoder Cookbook General TopCoder Cookbook Discussion Algorithm dynamic programming recipes Previous Thread  |  Next Thread