Dynamic Programming Flashcards
1
Q
What are the two main techniques used in Dynamic Programming?
A
Memoization (Top-Down), Tabulation (Bottom-Up).
2
Q
What is the difference between top-down (memoization) and bottom-up (tabulation) DP?
A
Memoization uses recursion + caching, Tabulation uses loops.
3
Q
What is the time complexity of solving Fibonacci with DP?
A
O(n).
4
Q
How does the Knapsack problem use DP?
A
Optimize item selection within weight constraints.
5
Q
What is the longest common subsequence (LCS) problem, and how is it solved?
A
Find the longest common sequence in two strings.
6
Q
What is the difference between DP and Greedy algorithms?
A
DP finds global optimal, Greedy finds local optimal.
