What is dynamic programming?

Answer 1

Dynamic programming is a technique for solving problem and come up an algorithm. Dynamic programming divide the problem into subparts and then solve the subparts and use the solutions of the subparts to come to a solution.The main difference b/w dynamic programming and divide and conquer design technique is that the partial solutions are stored in dynamic programming but are not stored and used in divide and conquer technique.

Answer 2

Dynamic Programming is a crucial concept in programming. Dynamic programming is a technique that divides a problem into smaller ones and saves the answer for later time without having to recalculate it. The optimal substructure property refers to the optimization of the subproblems in order to maximize the overall solution. Dynamic programming is mainly used to address optimization issues. In this context, optimization challenges refer to situations where we are attempting to determine the minimal or maximum solution to a problem. If a solution does exist, dynamic programming ensures that the best solution will be found.

According to the definition of dynamic programming, it is a method for solving complex problems by first decomposing them into a number of simpler subproblems, solving each subproblem only once, and then storing the answers to prevent having to perform the same calculations repeatedly.

Now, let's see how the dynamic programming approach works. Following are the steps included in dynamic programming:

It breaks down complicated problems into smaller subproblems.

Then, it determines the best solution for each of these smaller subproblems.

It stores the output of the subproblems (memoization). Memorization is the process of storing the answers to the subproblems.

It makes use of them again so that the identical sub-problem can be calculated more than once.

Calculate the outcome of the complex problem last.

Remember, you can apply Dynamic Programming to a specific type of problem—the subproblems with overlapping solutions and the optimal substructures.

Here, the term "optimal substructure" refers to the fact that optimization issues can be solved by merely integrating the best solutions to all their subproblems.

Dynamic programming would result in a higher space complexity because the intermediate outputs would need to be stored but have a lower time complexity.

There are two types of approaches that you can use in dynamic programming:

Top-down approach,

Bottom-up approach.

The top-down approach of dynamic programming uses the memoization technique, but the bottom-up approach uses the tabulation technique.

Here, memoization is the addition of caching and recursion. Caching involves saving the interim results, whereas recursion is the process of calling a method by itself.

The bottom-up method uses the tabulation technique to implement dynamic programming. It eliminates the recursion while still solving the same kind of issues. If we remove the recursion, the problem with stack overflow and the overhead of the recursive functions go away. We solve the problems and input the solutions into a matrix with this tabulation technique.

You can use the bottom-up approach in case you want to avoid recursion. The bottom-up approach also helps in saving memory.

A bottom-up algorithm begins at the beginning, whereas a recursive algorithm begins at the end and goes backward. In the bottom-up method, we start with the base case and work our way up to the solution.

I hope this answer addresses all your queries. Happy Coding!!