Which of these problems is well-suited for a top-down dynamic programming approach?
Calculating the factorial of a number.
Finding the Fibonacci sequence.
Sorting an array of integers in ascending order.
Finding the shortest path in a directed acyclic graph.
What is the fundamental principle behind dynamic programming?
Always choosing the locally optimal choice
Breaking down problems into smaller, overlapping subproblems
Using brute-force to explore all possible solutions
Sorting data to find the optimal solution
Which of the following terms is NOT directly related to dynamic programming?
Memoization
Tabulation
Divide and conquer
Optimal substructure
What is the primary benefit of using a top-down dynamic programming approach (memoization) over a purely recursive approach?
It eliminates the need for recursion entirely.
It avoids redundant computations by storing and reusing previously calculated results.
It reduces the need for complex data structures.
It improves the asymptotic time complexity of all algorithms.
What is the difference between memoization and tabulation in dynamic programming?
Memoization stores results in a table, while tabulation uses a recursive stack.
Memoization is less efficient than tabulation in terms of space complexity.
Memoization uses iteration, while tabulation uses recursion.
Memoization solves the problem top-down, while tabulation solves it bottom-up.
What is the core principle behind the bottom-up approach (tabulation) in dynamic programming?
Using recursion to break down the problem into smaller subproblems.
Solving the problem in reverse order of subproblems.
Building a table of solutions to subproblems, starting from the smallest subproblems and moving up.
Applying a greedy algorithm to find a locally optimal solution at each step.
Which of the following best describes the principle of overlapping subproblems in dynamic programming?
Finding the optimal solution without considering all possible solutions.
Breaking down a problem into smaller, independent subproblems.
Solving the same subproblems multiple times, leading to redundant computations.
Storing and reusing the results of already solved subproblems.
Which of the following is a real-world application of dynamic programming?
Finding the optimal strategy for playing a game of chess.
Sorting a list of customer names.
Displaying a webpage in a web browser.
Sending an email.
Which data structure is commonly used to implement the tabulation table in a bottom-up dynamic programming solution?
A binary tree.
An array or a matrix.
A stack.
A linked list.
Which of the following is a common technique for implementing memoization in a top-down dynamic programming solution?
Employing a recursive function with a cache (like a dictionary or array) to store results.
Using a stack data structure.
Converting the problem into an iterative approach.
Sorting the input data before processing.