What do you mean by Dynamic programming strategy? Explain the element of DP.

Question

Suresh Chand · Accepted Answer

The dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, the results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems. Dynamic programming is used where we have problems, which can be divided into similar sub-problems so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, the dynamic algorithm will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best solution. So we can say that − The problem should be able to be divided into smaller overlapping sub-problem. An optimum solution can be achieved by using an optimum solution of smaller sub-problems. Dynamic algorithms use Memoization. If the problem has an optimal substructure, then we can recursively define an optimal solution. If a problem has overlapping sub-problems, then we can improve on implementation by computing each sub-problem only once. Element of Dynamic Programming: There are basically three elements that categorize a dynamic programming algorithm: 1. Substructure: Decompose the given program into smaller sub-problems. Express the solution of the original problem in terms of the solution for smaller problems. 2. Table Structure: After solving the sub-problems, store the results of the sub-problems in a table. This is done because sub-problem solutions are reused many times, and we do not want to repeatedly solve the same problem over and over again. 3. Bottom-up Computation: Using the table, combine the solution of smaller sub-problems to solve larger sub-problems and eventually arrives at a solution to complete the problem.

What do you mean by Dynamic programming strategy? Explain the element of DP.

Leave your Answer:

Hits Counter

Question

What do you mean by Dynamic programming strategy? Explain the element of DP.

Leave your Answer: