Why is dynamic programming often preferred over a purely recursive approach for problems with overlapping subproblems?
Dynamic programming avoids the function call overhead associated with recursion, leading to better time complexity.
Dynamic programming is easier to implement and understand than recursion.
Recursion cannot solve problems with overlapping subproblems.
Dynamic programming always uses less memory than recursion.
Which of these problems is well-suited for a top-down dynamic programming approach?
Finding the shortest path in a directed acyclic graph.
Calculating the factorial of a number.
Finding the Fibonacci sequence.
Sorting an array of integers in ascending order.
Which of these problems is typically NOT solved using dynamic programming?
Computing the edit distance between two strings
Solving the knapsack problem
Finding the longest common subsequence of two strings
Finding the convex hull of a set of points
Who is credited as the pioneer of dynamic programming?
Donald Knuth
Alan Turing
Edsger W. Dijkstra
Richard Bellman
Which statement best describes the difference between top-down and bottom-up approaches in dynamic programming?
Top-down is generally less efficient than bottom-up
Top-down solves the main problem first, while bottom-up starts with subproblems
Top-down uses recursion, while bottom-up uses iteration
Top-down is more intuitive for understanding the problem, while bottom-up is better for optimization
Which of the following is a real-world application of dynamic programming?
Finding the optimal strategy for playing a game of chess.
Sending an email.
Displaying a webpage in a web browser.
Sorting a list of customer names.
Which of the following terms is NOT directly related to dynamic programming?
Memoization
Tabulation
Optimal substructure
Divide and conquer
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.
How does dynamic programming approach the problem of overlapping subproblems?
It uses heuristics to approximate the solutions to overlapping subproblems
It employs backtracking to explore all possible solutions to overlapping subproblems
It avoids overlapping subproblems altogether by breaking down the problem differently
It solves each subproblem only once and stores its solution for later reuse
Which data structure is commonly used to implement the tabulation table in a bottom-up dynamic programming solution?
A binary tree.
A stack.
A linked list.
An array or a matrix.