Now, when we've seen several examples, let's summarize. So we've discussed already several times the most important and probably the most creative step in designing a dynamic programming solution is defining the subproblem, and writing down a recurrence relation allowing us to express a solution for a subproblem through solutions to smaller subproblems. There are two common ways of doing this. The first way is by analyzing the structure of an optimal solution. And the second way is by, first, implementing a brute force solution and then optimizing it. Let me also remind you how subproblems look like for all the problems that we can see relating to these two modules. So the first one is the longest increase in subsequence. In this case, we defined the subproblem as specified by parameter I, to be the length of an optimal increase in subsequences. The longest increase in subsequences ending is the I's element. In the edit distance problem where we need to find the edit distance between two given strings, the subproblem was essentially the same problem, computing the edit distance between two prefixes of a given two strings. For the knapsack problem where our goal was to fill in the bag of capacity W with items. Optimally, we were solving subproblems for bags of smaller capacities. Finally, for the chain matrix multiplication where we are given N matrices and we need to multiply them optimally, I mean in an optimal cost, our subproblems were multiplying some contiguous subsequences of our N matrices. So in general, when you have a problem specifying a sequence or two sequences or three or something, in many cases the subproblem is defined by considering subsequences or prefixes or subtrees of the initial sequence. Still it requires creativity, of course, and practice to define the right notion of a subproblem. So when the recurrence relation on subproblems is written down, it is a technicality to convert it into a recursive algorithm. So, for this you store the result of all subproblems in some table, and before computing the result for a particular subproblem you first check whether it is already stored in the table or not. If it is stored you return it immediately. So you start computing it only if you haven't computed it so far. The next natural step is to convert a recursive algorithm into an iterative one. This usually requires just initializing the table and then fill going from smaller subproblems to larger subproblems. In particular, this usually requires one to specify an order on all subproblems. Right? The next step is proving an upper bound on the running time of the result in the algorithm. In many cases, a reasonable estimate is just to compute the number of subproblems and to multiply it by the time taken to compute the solution for each subproblem. The next step is to also implement unwind solutions. So in many cases, your first dynamic programming solution only computes cost of an optimal solution. And to find an optimal solution itself, you usually use a table to unwind an optimal solution. You use a table of solution of all subproblems. The next step is actually exploiting the structure of the table of your iterative solution in order to check whether you can save space. For example, as you remember in case of the knapsack problem, or in case of the edit distance problem, instead of storing the whole table one can store just the current row and the previous row or the current column and the previous column. This reduces the space requirement from quadratic to linear. Finally, let's discuss advantages of recursive and iterative approach. So the first advantage of an iterative approach is that there is no recursion overhead in this case. So instead of making recursive calls, we're just filing in where there is a table. And we're also using simpler data structure just arrays instead of dictionaries, for example. Another advantage is that just by looking at the table and the way it is filled in you can actually save space. Again, the example is the edit distance problem and the knapsack problem, for example, where instead of storing the whole table it is enough to store the current row and the previous row, for example. At the same time, the advantages of the recursive approach are the following; a recursive approach can still be faster and that happens in cases where not all the subproblems need to be solved. A good illustration of such a situation is the knapsack problem as we've discussed already. In the case when all the weights are divisible by some common factor, for example 100, we are only interested in subproblems where the capacity of a bag is divisible by 100. And, the recursive approach will only solve such subproblems while the iterative approach in this case will solve just all possible subproblems, not only those where the capacity are divisible by 100. In this case the recursive approach might be faster. So this depends on the data set but still. Another advantage is that sometimes it is easier to implement a recursive approach just because in this case, you did not need to specify the order of subproblems explicitly. So the recursion will find its way to the answer itself.
