From the course: Fundamentals of Dynamic Programming
Unlock this course with a free trial
Join today to access over 22,600 courses taught by industry experts.
Recap of dynamic programming - Python Tutorial
From the course: Fundamentals of Dynamic Programming
Recap of dynamic programming
- [Instructor] Dynamic programming is a technique for computing a recursive algorithm with a highly overlapping sub-problem structure. Dynamic programming achieves efficiency by solving each sub problem only once. A classic example of such a recursive algorithm is the one used to compute the Fibonacci sequence. Implemented in a straightforward way, the algorithm takes exponential time. The first technique for avoiding a repeated work is memoization, which caches the results of repeated calculations. This trades off speed at the expense of memory usage. The other technique is bottom-up dynamic programming. In this technique, we solve earlier sub problems first and throw away intermediate values when they're no longer needed. In turn this results in efficient time and space complexity. With either of these techniques, you will be able to solve many difficult problems efficiently.
Practice while you learn with exercise files
Download the files the instructor uses to teach the course. Follow along and learn by watching, listening and practicing.