Which statement best describes the difference between top-down and bottom-up approaches in dynamic programming?
Top-down solves the main problem first, while bottom-up starts with subproblems
Top-down is more intuitive for understanding the problem, while bottom-up is better for optimization
Top-down is generally less efficient than bottom-up
Top-down uses recursion, while bottom-up uses iteration
What is the difference between memoization and tabulation in dynamic programming?
Memoization stores results in a table, while tabulation uses a recursive stack.
Memoization uses iteration, while tabulation uses recursion.
Memoization is less efficient than tabulation in terms of space complexity.
Memoization solves the problem top-down, while tabulation solves it bottom-up.
The computation of the nth Catalan number can be efficiently performed using dynamic programming. What is the primary advantage of employing dynamic programming in this scenario?
Dynamic programming improves the space complexity but does not affect the time complexity.
Catalan numbers have a closed-form solution, making dynamic programming unnecessary.
Dynamic programming eliminates the need for recursion.
Dynamic programming reduces the time complexity from exponential to linear.
Dynamic programming is often used in optimizing which aspect of algorithms?
Data structure usage
Time complexity
Code readability
Space complexity
What is the core principle behind the bottom-up approach (tabulation) in dynamic programming?
Solving the problem in reverse order of subproblems.
Building a table of solutions to subproblems, starting from the smallest subproblems and moving up.
Using recursion to break down the problem into smaller subproblems.
Applying a greedy algorithm to find a locally optimal solution at each step.
How does Dynamic Programming differ from a greedy algorithm?
Greedy algorithms make locally optimal choices, while Dynamic Programming considers all subproblems.
Dynamic Programming always results in a faster solution than a greedy algorithm.
Dynamic Programming cannot be used to solve problems that can be solved with a greedy algorithm.
Greedy algorithms always find the globally optimal solution.
Which of the following best describes the principle of overlapping subproblems in dynamic programming?
Storing and reusing the results of already solved subproblems.
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.
A problem can be solved using dynamic programming if it has:
Both overlapping subproblems and optimal substructure
Neither overlapping subproblems nor optimal substructure
Optimal substructure
Overlapping subproblems
Which data structure is commonly used to implement the tabulation table in a bottom-up dynamic programming solution?
A linked list.
A binary tree.
A stack.
An array or a matrix.
Which of the following terms is NOT directly related to dynamic programming?
Memoization
Tabulation
Divide and conquer