Fundamentals of Dynamic Programming

Course details

Having a clearer picture of dynamic programming (DP) can take your coding to the next level. It's a technique that makes it possible to adeptly solve difficult problems, which is why it comes up in interviews and is used in applications like machine learning. In this course, learn about the uses of DP, how to determine when it’s an appropriate tactic, how it produces efficient and easily understood algorithms, and how it's used in real-world applications. Compare different approaches to computing the Fibonacci Sequence and learn how to visualize the problem as a directed acyclic graph. Explore the different variations of DP that you’re likely to encounter by working through a series of increasingly complex challenges. Plus, build a content-aware image resizing application with these new concepts at its core.

Concepts

0. Introduction

01 - The importance of dynamic programming
02 - What you should know

1. Introduction to Dynamic Programming

03 - What is dynamic programming
04 - The Fibonacci sequence
05 - Speeding up calculations with memoization
06 - Bottom-up approach to dynamic programming
07 - Recap of dynamic programming

2. Examples of Dynamic Programming

08 - Planting flowers in a flowerbox
09 - Breaking down the flowerbox problem into subproblems
10 - Solving the flowerbox problem in Python
11 - How many ways can you make change
12 - Breaking down the change-making problem into subproblems
13 - Solving the change-making problem in Python

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

14 - What is content-aware image resizing
15 - Preprocessing - Defining the energy of an image
16 - Project - Calculating the energy of an image
17 - Solution - Calculating the energy of an image
18 - Using dynamic programming to find low-energy seams
19 - Project - Finding low-energy seams
20 - Solution - Finding low-energy seams
21 - Project - Using backpointers to reconstruct seams
22 - Solution - Using backpointers to reconstruct seams
23 - Project - Removing low-energy seams
24 - Solution - Removing low-energy seams

4. Dynamic Programming for Machine Learning - Hidden Markov Models

25 - What is a Hidden Markov Model
26 - Modeling a Hidden Markov Model in Python
27 - Inferring the most probable state sequence
28 - Breaking down state inference into subproblems - The Viterbi algorithm
29 - Implementing the Viterbi algorithm in Python
30 - More applications of Hidden Markov Models
31 - Training Hidden Markov Models

Conclusion

32 - Next steps