Fundamentals of Dynamic Programming

Dynamic programming makes it possible to solve challenging problems efficiently. Learn what it is, how and when to apply it to your algorithms, and how it's used in applications.

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