In today’s article, AlgoMonster will provide a detailed example that shows how to efficiently solve a difficult problem using dynamic programming and recursion. You can solve it either with memoization or tabulation. Let’s see what’s the difference.
Table of Contents
Definitions of the concepts
First of all, look at what these concepts are all about.
Dynamic programming
A dynamic programming algorithm solves complex problems. How does it solve it? Well, it breaks them into smaller subproblems. Then, it solves each of them only once. Next, it caches the results of each subproblem. Finally, you will get the optimal solution for the entire problem when you combine the results of the subproblems.
What is memoization?
Memoization is an optimization technique that speeds up programs in solving problems. How does it work? Generally, it saves the results of expensive function calls and returns them when you need the results again. The main purpose is to avoid repetition and save time.
Tabulation in dynamic programming
Tabulation is a optimization tool often used in dynamic programming. It solves DP problems like this: fill out a table and then calculate the result to the original problem using results from the table.
A great example of dynamic programming solving problems
Problem statement: say, you just received a tube of chocolates that you plan to eat every day. That is to say, you are going to eat one piece of it each day.
Every piece of it has a positive integer, which indicates how delicious it is. There is an expectancy factor, which is a subjective measure of taste. If you eat a piece later, it will taste better: If the taste is m (as hmm), it will be km by day number k.
You have to code a method that calculates the best chocolate-eating strategy for you. Also, it tells how much pleasure you can expect.
Recursive algorithm:
The function can solve a slightly different problem than the one described. And it calculates your total pleasure if the first bite is taken at a particular time. This strategy is what programmers usually use for writing recursive codes.
It’s not hard to notice that this code returns the correct result. The function returns the correct value in the base case where choco has only one element.
If choco has n elements, we must start with choco[0] and choco[n-1], and n is greater than 1. The code returns the maximum pleasure for each case with recursion.
Dynamic programming with memoization
Although the code is very simple, it’s extremely inefficient. Worse still, it also has exponential time complexity.
Yet, the recursive functions perform the exact same computations. The only values that must be computed are
joy(choco[i:j], day)
where 0 <= i = j = n, day = 1+ n -(j – i), and n = len (choco).
The joy of choco[i]j can either be calculated directly (the base) or in constant time using the choco[i+1,j] and choco[i-1:j-1). We can create an algorithm with O(n2) complexity if we use dynamic programming.
This strategy can be implemented using memoization by including the indexes in the function calls. We keep track of which options (left or right), that give us the best pleasure to help us record an optimal solution.
With this memo table, it’s easy to schedule an optimal eating order:
Dynamic programming using tabulation
Alternatively, you can use tabulation to fill up the memo table. However, it is important to note that the order of computation is crucial. To compute the value memo[i][j], it must be first known the memo[i+1][j] values.
With the above table, it’s easy to get the result of the optimal eating order as before.
Is recursion also DP?
Recursion has been mentioned several times in the past. You might be curious what recursion means. What is the difference between recursion and DP?
Wikipedia says memoization is one of the most important ideas in computer science. Niklaus Wirth said and here we quote:
“The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.”
Recursion is when the same approach is used repeatedly to solve the same sub-problems. A recursion is a top-down approach. Recursion is often referred to as dynamic programming’s parent.
Dynamic programming increases efficiency by eliminating the risk of having to recalculate similar problems as recursion. However, dynamic programming problems can be solved with recursion.
Final thoughts: Memorization or tabulation?
It is mostly personal preference that determines whether to memoize or tabulate. If subproblems are not required to be solved, however, memoization may prove more efficient as only the calculations that are needed are performed.