Dynamic Programming Flashcards
1
Q
Dynamic programming definition
A
A technique to solve a hard problem by breaking it into sub problems and solving those first
2
Q
Dynamic programming and dependencies
A
It does not work when sub problems depend on each other. It only handles discrete sub problems
3
Q
Knapsack problem
A
Dynamic programming is good when you are trying to optimize something given a restraint.
4
Q
When can you use dynamic programming
A
When the problem can be broken into discrete sub problems that don’t depend on each other.
5
Q
Characteristics of dynamic programming
A
The solution always has a grid
The values are usually what you are trying to optimize
Each cell is a sub problem
There is a constraint ie time weight
