With bottom up dp, one can easily optimize memory usage for some type of problems. CMIIW.

Beside to uptimist comment , i think that bottom up dp is easier to debug

Not always true — that recursive is more "mathematical" — I think using for loops makes it easier to realize the invariant, catch errors, plus you don't have to think about the recursion stack overflow chance.

Using iterative dp allows you to optimize the running time, this makes easier to handle how to compute the values and that's the trick to apply dp optimizations (memory space and time). Is very common to see problems that using prefix sums can reduce running time by a factor of N (to mention an example). And usually the code is shorter.

Edit: Here you have a sample problem 611D - New Year and Ancient Prophecy

In almost every case iterative dynamic programming solution is much faster than recursion and then it's just a habit to write optimal solutions even if suboptimal will also work.

It's like when you need a function to check if the number is prime. I'm sure, 99% of the people will write a function which checks divisors upto sqrt(N), even if the solution with checking upto N would also pass.

Talking about your statement "there are enough cases where recursion performs better because it visits fewer states, while arrays will always visit EVERY state.". I don't agree that there's enough such cases. In most problems for maximum test recursion will visit every state, and if it's not the case (which is pretty rare) then be sure that top programmers will write a solution with the recursion.

Though I am not top rated.

But I do not know how can we data structural optimization to recursive DP? I have never faced a TLE in Non recursive dp while I have when I wrote top down, then why will I take any chance? The only time I will probably write a recursive implementation is only when I cannot understand topological ordering of the states!

I'd say there are several reasons.

Tradition

People are taught to implement dynamic programming using loops. Then they teach the next generation to implement dynamic programming using loops. Hardly surprising, regardless of whether they are right or not.

Convenience

To write loops instead of memoization, the required additional effort is to topologically sort the states in a loop-friendly way. This effort often pays off.

To begin with, the asymptotic complexity of a bunch of for loops is usually much more obvious than the complexity of a recursive solution. Furthermore, many advanced dynamic programming problems will require additional insights after figuring out the most obvious dynamic programming solution. There are often multiple ways to topologically sort the states, and some of them make optimizations possible — and visible. Some examples are computing prefix sums to speed things up (already mentioned a few times), or even getting rid of one of the parameters.

Forward and Backward Dynamic Programming

Often, we can express the objective function f(s) on state s as some combination of f(t₁), f(t₂), ..., f(t_k), much like a mathematical formula. This can be expressed as backward dynamic programming. At a certain point in time, we want to calculate f(s). Alright, take f(t₁), f(t₂), ..., f(t_k) — either they are already calculated with a loop-based solution, or we use recursion with memoization to calculate them as needed — and combine them in the required way (calculate their sum, maximum, or whatever). Here, we move from state s back to states t_i as needed.

However, some solutions are better expressed as forward dynamic programming. At a certain point in time, consider state s. At this point, f(s) is already calculated. We know that some states r₁, r₂, ..., r_p depend on state s. So, right now, we want to update the intermediate calculations in these states using f(s). When we later arrive at, say, r₁, it happens only when we already processed all states it depends on, and thus f(r₁) is already calculated. One example is Dijkstra's algorithm: whenever we add a vertex s to the tree of shortest paths, we update the minimum distance to each of the vertices r₁, r₂, ..., r_p directly reachable from s.

With this approach, we simply cannot write the mathematical formula like f(s) = G(f(t₁), ...) because the dependencies go the other way! Technically, it is still always possible to transform forward DP into backward DP (the entire graph between the states of dynamic programming can be stored, topologically sorted, and visited in the resulting order), but for some problems, forward DP can be more natural and more suitable for optimizations.

On a side note, I really like to see such things being discussed. Looking forward for more insightful answers!

I cannot agree that recursion is a more natural and mathematical way to write a solution. Loop-based code looks a lot like the inductive proof:

// Let's prove that our solution works by induction
f[0] = 1;               // Base is trivial
for (int i = 1; i <= n; // Suppose we are done for 0,...,i
i++)                    // Then let's prove for i+1
{ f[i] = i*f[i-1]; }    // Inductive step

In contrary, recursion looks like a mathematical formula only before you add memoizing.

1) Easy to debug 2) Loops can be optimized by compiler, and recursion is the thing compilers are afraid of. Also recursion need stack memory, what isn`t usually very big(1 mb, as far as I know in C++, ans much more less in python/php/etc) 3) because of previous fact loops are faster than recursion in non-functional programming languages(non-functional languages usually dont optimize tail recursion and functional ones must do this couse they have no loops in "classical" form) 4) memoized recursion needs global variables or work with pointers and loops do not.

I favor recursive solution, and this is why I do :

[1] Of course because I learned dp in recursive way :) and I think it's really great for beginners — because this way is easy to learn, and learning this way teaches more things. (backtracking, recursion, memoization, graph-theoretical thinking etc.)

[2] Finding the direction of loops are not always easy — For example, try to solve this problem in linear time with loops, and compare your code with recursive codes.

• You are given 2D matrix. You can move to adjacent cell if the value of the cell is strictly decreasing (like A[i][j] > A[i][j+1]). Now find the longest path in this grid.

Sometimes you need to optimize complicated backtracking code with memoization. It's also hard to find the direction of loop in that case, too.

[3] You can always change your recursive code to iterative code if you need to. However, some problem can't simply solved by iterations. Then, It's clear why we should learn dp in recursive way :)

[4] In my opinion, recursive dp is strong when you are dealing with messy DPs. I think this is true because of two reasons — you don't need to care the direction of loops & it's more easy to check base cases. less WA + less time -> more scores :)

(I have no idea how CF's auto numbering system behaves..)

I've wondered about this as well, what I've noticed is that some countries like Egypt only use recursive DP (all different universities/cities). I also find recursive solutions more "natural" but seeing that all reds use it, I'm now more inclined to use it as well. My guess is, when you're dealing with harder problems (maybe involving graphs/complex data structures) an "in-place" DP table solution is faster and more intuitive than passing whatever you're dealing with to a recursive function.

I use to code DP's with recursion. I always find hard to handle the base cases with the array method. However, it's a LOT easier to optimize the array-based DP. With a recursion, you can't use DP tricks like the Knuth Yao Optimization, the Convex Hull Trick, Range queries on previous states, memory optimizations (like the one used in the Knapsack Problem), etc (as far as I know).

Both methods have their pros and cons for some people. In my opinion, DP's with bitmasks states are easier to code as a recursion with memoization.

Haha, the writers of round 349 div. 2 must have read my question, because problem C forced me to use array-based DP instead of recursion due to the constraints. Thanks, writers! :-)