module 6 overview

*optimal solution structure for Divide & Conquer

*prev module greedy = make a decision based on what looks good right now / "on the spot"; 
	- that choice turns out to be good globally (part of global optimal solution)
	- reduces the problem to subproblems (not too many - usually one or two) 
	- very efficient, if that choice can be made without solving subpb first

* now DP = cannot make a good choice without solving subpb first
	- usually pick a subset of items/choices from a set that can only be done optimally by trying many possibitlities
	- will have to solve many problems to make a choice 
	- optimal solution structure still holds
	- only some of the pb will actually count for the overall solution

* 4 steps: we are breaking the methodology into 4 steps that are applicable to all DP solutions: optimal structure chacarterization, dynamic reccurence, bottom up computation, and tracing solution.

* examples: discrete knapsak, coin change, checkboard
* next module : LCS, Matrix Multiplication
* graphs later on : All Pair Shortest Path
--------------------------------------------------

module 7 overview

*this is a continuation of previous DP module, with slightly more complex examples. 

*Like before, we are breaking the methodology into 4 steps that are universal to DP solutions: recognizing the optimal solution structure, the reccurence, bottom-up computation and solution tracing (if necesary). 

* most divide & conquer problems can be solved with DP; some of them allow for greedy solutions. 
Its relatively easy to recognize and proof that a gredy solution works if thats the case; it is much harder to proof that no greedy approach can solve a problem - see 16.4-16.5 in the book for a discussion of greedy applicability.