Thursday, December 2, 2021
spot_img

Dynamic programming algorithm, Memoization strategy and Recursion

As 2 important programming concepts, many masses confuse dynamic programming with the recursion. What about memoization? Dynamic programming and the memoization are similar. Is dynamic programming and remembering the same thing with dissimilar names? To clarify these 3 basic techniques, AlgoMonster gives some of the information below for starters.

To separate these three apart, first thing first, we need to know what each of them is. Let’s start with dynamic programming.

What is dynamic programming?

Dynamic programming (also DP) is an algorithmic technique. It is used to solve a particular type of problem which shows a specific structure: optimal substructure. You can break an issue 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 stored for future use. That is to say, and 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 first dealing with all the related subproblems.

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 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 reencountering the same problem, you don’t need to do the exact 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 particular 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 subproblem only once. You can take memoization as a subset of DP. DP can solve problems that are solvable by memoization. Memoization solutions might cause a possible stack overflow. That is why issues that DP can solve 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 emotional 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.

  1. DP often includes memoization and recurrence. It is a strategy that we can use to solve similar smaller subproblems to solve the target problem.
  2. Memoization is just a form of caching that saves the values of a function. It is a technique to prevent you from doing the exact computation on the same problems.

Dynamic programming is a problem-solving solution that uses memoization to the full 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 repetition is in the possibility of defining an infinite set of objects by a finite statement. In a similar manner, an unlimited number of calculations ca describe by a finite recursive program, even if this program has 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. 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 mastering DP is through practice.

Related Articles

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Stay Connected

0FansLike
3,043FollowersFollow
0SubscribersSubscribe
- Advertisement -spot_img

Latest Articles