As two crucial programming concepts, many people confuse dynamic programming with recursion. What about memoization? Dynamic programming and memoization are quite similar indeed. Is dynamic programming and memoization the same thing with different names? To clarify these three basic techniques, AlgoMonster offers some information below for beginners.
To separate these three apart, first thing first, we need to know what each of them is. Let’s start with dynamic programming.
Table of Contents
What is dynamic programming?
Dynamic programming (also DP) is an algorithmic technique. It is used to solve a special type of problem which shows a specific structure: optimal substructure. You can break a problem of such kind into a collection of smaller subproblems. Each of its subproblems is similar to the original one. Having an optimal substructure allows us to solve small-sized problems, then medium problems, and big problems. We solve these problems in a particular order before we tackle the target problem at last.
Dynamic programming methods
Top-down (memoization): The big problem is solved by finding solutions to the subproblems. Answers to each of the subproblems will be stores for future use. That is to say, when the same problem occurs, you can directly use the result you saved instead of computing it one more time. You know, since similar subproblems repeat themselves many times, it saves a lot of time. The process of saving the previous results to avoid recomputing is referred to as the memoization technique.
Bottom-up (tabulation): Opposite to top-down, the bottom-up method avoids recursion by dealing with all the related subproblems first.
The bottom-up method is called tabulation as it is often done by populating into an n-dimensional table.
Differences between top-down and bottom-up
Put it into simpler words with an interesting analogy of how you take over the world:
Top-down with memoization
For the starter, you say I will conquer the world. How can you accomplish that goal? You declare I will take over Asia as a beginning. How can you achieve that? You say I will control Japan first. How so? I will become the president of Japan. How do you finish that? Just like that, you’ll finally find the solution to the bottom question.
Bottom-up with tabulation
First, you say I will become the president of Japan. After that, I will take over Japan. Then I will conquer other countries in Asia. Before I finally take over the world, I will capture the remaining continents. And that way, you come to your target.
So as the names indicate, they’re basically two opposite strategies for solving problems. The former goes with memoization while the latter with tabulation. Generally, the upward approach appears to be more efficient and cleaner.
What is memoization?
Memoization is for an optimization technique to track and store your previously solved solutions. When you encounter the same problem again, you don’t need to do the same computation since you can use the results you’ve cached.
Memoization and DP
Dynamic programming is to deal with problems of overlapping subproblems and optimal substructures. It is a method to solve certain classes of problems by solving recursion. At the same time, the DP solution saves the previously gained solutions via memoization or tabulation.
So both dynamic programming and memoization solve each individual subproblem only once. You can take memoization as a subset of DP. Problems that are solvable by memoization can be solved by DP. Memoization solutions might cause a possible stack overflow. That is why issues that can be solved by DP might not be suited for memoization solutions. Yet, DP can be more efficient because it’s iterative.
To recap: memoization is a common strategy for optimizing dynamic programming algorithms. This process relies on recursion. The purpose is to avoid calculating subproblems again that have been solved. And you could solve dynamic programming problems without recursion.
What is the difference between DP and memoization?
Some people regard memoization as just another name of DP. Or any tricks that use memoization are thought to be DP. But they’re different.
- DP often includes memoization and recurrence. It is a strategy that can be used when similar smaller subproblems can be solved to solve the target problem.
- Memoization is just a form of caching that saves the values of a function. It is a technique to prevent you from doing the same computation on the same problems.
Basically, dynamic programming is a problem-solving solution that uses memoization to the fullest effect.
Is recursion dynamic programming?
We’ve mentioned the term recursion several times above. You may be wondering what recursion is. What’s the difference between recursion and DP?
Well, according to Wikipedia, it is one of the main ideas of computer science. As Niklaus Wirth wrote in his book, and here I 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 solution is the repeated application of the same approach to the same type of sub-problems. Recursion follows a top-down approach. It’s safe to say that recursion can be regarded as the parent of dynamic programming.
Dynamic programming improves efficiency by solving the problem of risks to recompute the same problems recursion does. But you can deal with DP problems with recursion.
Conclusion
From the comparison above, hopefully, you’ve got some idea of what these concepts mean. This might not always be correct in some aspects, but you can regard this as a reference. Dynamic programming is just like recursion without repetition. In other words, DP and recursion share some similarities while DP avoids unnecessary recalculation. Simply put: DP only calculates the same subproblem once, but recursion may compute more than once.
Although they’re quite alike in certain aspects, they’re not the same. To tell them apart before you go on with your dynamic programming study is a wise choice. If you’re interested in DP, find more information. Read first, and then practice as much as you can. The key to master DP is through practice.
