31251 Lecture Notes - Lecture 6: Dynamic Programming
30 Jun 2018
School
Department
Course
Professor
Dynamic Programming
Dynamic programming looks a lot like Divide-and-Conquer, but subinstances overlap.
Usually implemented with some sort of table that keeps track of subinstance
solutions.
Normally they work bottom-up (the reverse of D&C):
Solve the smallest subinstances, combine them to make bigger subinstances, keep
going until you have the whole thing.
Can be done top-down (recursively) as well.
What makes it work?
Optimal Substructure: The same as greedy algorithms and D&C.
Overlapping Subproblems: As mentioned before.
Single Source Shortest Path
In unweighted graphs, the distance between two vertices is easy to calculate:
oJust do a breadth first search.
oIf you’re looking for a particular vertex, stop when you find it.
oThe distance is the same as the number of iterations taken to get to the
vertex.
In weighted graphs, it’s not so easy.
oThe lowest weight path is not always the path with fewest edges.
1 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
