# Data Structure Questions and Answers-Dynamic Programming

## Click on any option to know the CORRECT ANSWERS

 Question 1
Which of the following is/are property/properties of a dynamic programming problem?
 A Optimal substructure B Overlapping subproblems C Greedy approach D 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.

 Question 2
If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ..... property.
 A Overlapping subproblems B Optimal substructure C Memoization D Greedy

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.

 Question 3
If a problem can be broken into subproblems which are reused several times, the problem possesses ..... property.
 A Overlapping subproblems B Optimal substructure C Memoization D Greedy

Question 3 Explanation:
Overlapping subproblems is the property in which value of a subproblem is used several times.

 Question 4
If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called .....
 A Dynamic programming B Greedy C Divide and conquer D Recursion

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.

 Question 5
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.
 A True B False