Dynamic Programming Basics

Evaluate optimal substructure and memoization.

1. Which of the following is a core property of problems suitable for dynamic programming?

Non-overlapping subproblems Optimal substructure Randomized subproblems Greedy substructure

2. What term describes storing results of expensive function calls to return cached results for repeated inputs in dynamic programming?

Tabulation Memoization Recursion Iteration

3. Which dynamic programming approach solves subproblems iteratively and stores results in a table?

Top-down Memoization Bottom-up Recursive

4. Select all key characteristics of problems solvable by dynamic programming.

Overlapping subproblems Optimal substructure Independent subproblems Exponential time complexity

5. Which of the following are classic dynamic programming problems?

Fibonacci sequence calculation Longest Common Subsequence (LCS) Merge Sort 0-1 Knapsack Problem

6. Dynamic programming can only be implemented using a recursive approach.

True False

7. The Fibonacci sequence problem exhibits overlapping subproblems, making it suitable for dynamic programming.

True False

8. What does the acronym 'DP' stand for in the context of algorithm design?

9. In dynamic programming, the top-down approach is also known by what name involving caching subproblem results?

10. Name the dynamic programming approach that starts by solving the smallest subproblems first (two words).

Answered 0 of 0 — 0 correct

Company