Fundamentals of Dynamic Programming

Introduction

• The importance of dynamic programming
• What you should know

1. Introduction to Dynamic Programming

• What is dynamic programming?
• The Fibonacci sequence
• Speeding up calculations with memoization
• Bottom-up approach to dynamic programming
• Recap of dynamic programming

2. Examples of Dynamic Programming

• Planting flowers in a flowerbox
• Breaking down the flowerbox problem into subproblems
• Solving the flowerbox problem in Python
• How many ways can you make change?
• Breaking down the change-making problem into subproblems
• Solving the change-making problem in Python

3. Real-World Dynamic Programming: Content-Aware Image Resizing

• What is content-aware image resizing?
• Preprocessing: Defining the energy of an image
• Project: Calculating the energy of an image
• Solution: Calculating the energy of an image
• Using dynamic programming to find low-energy seams
• Project: Finding low-energy seams
• Solution: Finding low-energy seams
• Project: Using backpointers to reconstruct seams
• Solution: Using backpointers to reconstruct seams
• Project: Removing low-energy seams
• Solution: Removing low-energy seams

4. Dynamic Programming for Machine Learning: Hidden Markov Models

• What is a Hidden Markov Model?
• Modeling a Hidden Markov Model in Python
• Inferring the most probable state sequence
• Breaking down state inference into subproblems: The Viterbi algorithm
• Implementing the Viterbi algorithm in Python
• More applications of Hidden Markov Models
• Training Hidden Markov Models

Conclusion

• Next steps