Data Structure Questions and Answers – Dynamic Programming

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Dynamic Programming”.

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
View Answer

Answer: d
Explanation: A problem that can be solved using dynamic programming possesses overlapping subproblems as well as optimal substructure properties.

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
View Answer

Answer: b
Explanation: Optimal substructure is the property in which an optimal solution is found for the problem by constructing optimal solutions for the subproblems.

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
View Answer

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

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
View Answer

Answer: c
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.

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
View Answer

Answer: a
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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. A greedy algorithm can be used to solve all the dynamic programming problems.
a) True
b) False
View Answer

Answer: b
Explanation: A greedy algorithm gives optimal solution for all subproblems, but when these locally optimal solutions are combined it may NOT result into a globally optimal solution. Hence, a greedy algorithm CANNOT be used to solve all the dynamic programming problems.

7. In dynamic programming, the technique of storing the previously calculated values is called ___________
a) Saving value property
b) Storing value property
c) Memoization
d) Mapping
View Answer

Answer: c
Explanation: Memoization is the technique in which previously calculated values are stored, so that, these values can be used to solve other subproblems.
advertisement

8. When a top-down approach of dynamic programming is applied to a problem, it usually _____________
a) Decreases both, the time complexity and the space complexity
b) Decreases the time complexity and increases the space complexity
c) Increases the time complexity and decreases the space complexity
d) Increases both, the time complexity and the space complexity
View Answer

Answer: b
Explanation: The top-down approach uses the memoization technique which stores the previously calculated values. Due to this, the time complexity is decreased but the space complexity is increased.

9. Which of the following problems is NOT solved using dynamic programming?
a) 0/1 knapsack problem
b) Matrix chain multiplication problem
c) Edit distance problem
d) Fractional knapsack problem
View Answer

Answer: d
Explanation: The fractional knapsack problem is solved using a greedy algorithm.
advertisement

10. Which of the following problems should be solved using dynamic programming?
a) Mergesort
b) Binary search
c) Longest common subsequence
d) Quicksort
View Answer

Answer: c
Explanation: The longest common subsequence problem has both, optimal substructure and overlapping subproblems. Hence, dynamic programming should be used the solve this problem.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.