15 Dynamic Programming Flashcards
1
Q
How is dynamic programming similar to divide and conquer?
A
Both solve complex problems by breaking them into smaller, easier to solve subproblems.
2
Q
How is dynamic programming different to divide and conquer?
A
The subproblems solved by dynamic programming are not independent, and are repeatedly encountered in different contexts.
3
Q
What is Dynamic Programming effective for?
A
Problems where the same subproblem needs to be solved repeatedly.
4
Q
Every dynamic programming algorithm uses:
A
A table that has one entry for each subproblem.
5
Q
The development of a dynamic programming has 3 Key components:
A
- The recurrence relation (for defining the value of an optimal solution)
- The tabular computation (for computing the value of an optimal solution)
- The traceback (for extracting an optimal solution).
6
Q
Longest common String Running Time
A
O(m*n)
