
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 (topdown and bottomup 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 componentwise <=. Not sure that I should write a lot here since it is the usual DP. 5. Subsets, ordered by inclusion Here 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 ancestry Here should be a note about time complexity analysis. 8. With profiles + broken profiles.
General optimizations: 9. Parameter dependence in solution space Eliminating 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 divideandconquer 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 solutionresult 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. 