What is a key advantage of using dynamic programming (memoization or tabulation) over a purely recursive approach for the Coin Change problem?
Dynamic programming makes the solution easier to understand.
Dynamic programming reduces the space complexity of the solution.
Dynamic programming always finds a solution, while recursion might not.
Dynamic programming avoids redundant calculations, improving efficiency.
The Longest Common Subsequence problem exhibits which of the following properties that make it suitable for Dynamic Programming?
Backtracking
Greedy Choice Property
Optimal Substructure and Overlapping Subproblems
Divide and Conquer
In the context of edit distance, what does a diagonal transition in the dynamic programming table represent?
Insertion of a character
Matching of two characters
Deletion of a character
Substitution of a character
What is the base case in the recursive approach for calculating Levenshtein distance?
When both strings are identical.
When the edit distance is zero.
When both strings have the same length.
When one or both strings are empty.
How does memoization improve the efficiency of the recursive solution for LIS?
It eliminates tail recursion, making the solution iterative.
It sorts the input sequence to reduce the search space.
It converts the recursive solution into a dynamic programming solution.
It stores the results of overlapping subproblems to avoid recomputation.
What is the primary purpose of using dynamic programming to calculate the Levenshtein distance?
To sort a list of strings in lexicographical order.
To determine if two strings are anagrams of each other.
To reduce the time complexity by storing and reusing previously computed distances.
To find all possible edit operations between two strings.
How does memoization improve the efficiency of the recursive solution for Levenshtein distance?
It converts the recursive solution into an iterative one.
It reduces the depth of the recursion tree.
It sorts the input strings to speed up comparisons.
It avoids redundant calculations by storing and reusing previously computed distances.
In a Dynamic Programming solution for LCS, what does a cell in the DP table typically represent?
The maximum length of the LCS found so far.
The cost of inserting, deleting, or replacing a character to make the prefixes of the input sequences equal.
The length of the LCS of the prefixes of the input sequences up to those indices.
Whether the characters at those indices in the input sequences are the same.
What does each cell in the tabulation table typically store in the dynamic programming solution to the Coin Change problem?
The remaining amount to be formed.
The minimum number of coins required to make change for a specific amount using a subset of coin denominations.
The total value of coins used so far.
Whether or not a particular coin denomination is used in the optimal solution.
How does memoization optimize the recursive solution for the 0/1 Knapsack problem?
It uses a greedy approach to select items.
It stores the results of overlapping subproblems to avoid redundant computations.
It transforms the problem into a simpler, equivalent problem.
It sorts the items by their weight-to-value ratio.