Data Structure Questions and Answers-Dynamic Programming
Click on any option to know the CORRECT ANSWERS
Which of the following is/are property/properties of a dynamic programming problem?
Both optimal substructure and overlapping subproblems
Question 1 Explanation:
A problem that can be solved using dynamic programming possesses overlapping subproblems as well as optimal substructure properties.
If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ..... property.
Question 2 Explanation:
Optimal substructure is the property in which an optimal solution is found for the problem by constructing optimal solutions for the subproblems.
If a problem can be broken into subproblems which are reused several times, the problem possesses ..... property.
Question 3 Explanation:
Overlapping subproblems is the property in which value of a subproblem is used several times.
If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called .....
Divide and conquer
Question 4 Explanation:
In divide and conquer, the problem is divided into smaller non-overlapping subproblems and an optimal solution for each of the subproblems is found. The optimal solutions are then combined to get a global optimal solution. For example, mergesort uses divide and conquer strategy.
When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don't take advantage of overlapping subproblems.
Question 5 Explanation:
Dynamic programming calculates the value of a subproblem only once, while other methods that don't take advantage of the overlapping subproblems property may calculate the value of the same subproblem several times. So, dynamic programming saves the time of recalculation and takes far less time as compared to other methods that don't take advantage of the overlapping subproblems property.
There are 5 questions to complete.