Proof of Induction and DP

###Proof of induction

Try sometimes induction on portion of the whole problem.

Induction can be only a component of the whole proof, try simplify the problem then use induction as the last step to close the loop.

###Proof of DP

####3M: Meaning, Method, Meat

• Meaning of each entry in the table
• Method to fill the table (and sequence)
• Meat: how to get the result (post-processing)

####Pattern(Must say in prooving DP)

1. Consider an entry in the table
2. Consider the optimal way to get there
3. Consider the last choice you made in an optimal solution to get there