Dynamic Programming

Question 1

Dynamic programming definition

Answer 1

A technique to solve a hard problem by breaking it into sub problems and solving those first

Question 2

Dynamic programming and dependencies

Answer 2

It does not work when sub problems depend on each other. It only handles discrete sub problems

Question 3

Knapsack problem

Answer 3

Dynamic programming is good when you are trying to optimize something given a restraint.

Question 4

When can you use dynamic programming

Answer 4

When the problem can be broken into discrete sub problems that don’t depend on each other.

Question 5

Characteristics of dynamic programming

Answer 5

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