Top 5 Books on Dynamic Programming for Beginners (2020)

IMG_20200716_221604+%281%29.jpg

As a programmer, you may feel fear and frustration whenever you hear the phrase “dynamic programming.”

You may actively be avoiding dynamic programming as we speak, finally mustering up the courage to look it up or purchase a book.

It’s a scary topic, but it will put you ahead in your coding interviews and improve you as a programmer.

And it’s true: dynamic programming concepts are challenging to grasp and apply. If you learn programming by looking for repeatable and reusable patterns, you’ll struggle with dynamic programming — since, after all — it’s dynamic.

With dynamic programming, patterns are tricky and difficult to master. Despite endless hours of research and trial and error, you may feel like you haven’t made that much progress. This is especially true if you’re trying to learn as much as you can in a short amount of time. 

With the books on dynamic programming by your side, you’ll be amazed by how much easier dynamic programming problems can become. Today, we’re going to talk about the top five books that can help you learn dynamic programming.

 

READ THE SERIES ON ALGORITHMS AND CODING INTERVIEWS

Other Books on Code articles about solving complex programming problems:


What Is Dynamic Programming?

Finding the coins needed for a specific value is a common problem that can be solved with dynamic programming.

Finding the coins needed for a specific value is a common problem that can be solved with dynamic programming.

Before we jump into our list, you still may be fuzzy about what ‘dynamic programming’ is. The term itself is a bit loaded, with dynamic being a broad word that can apply to many things. So really, what is dynamic programming?

First of all, the concept of recursion is a prerequisite to understanding dynamic programming. If you do not already have a foundation in data structures & algorithms, I highly recommend studying Grokking Algorithms first, which is the same book that introduced me to these concepts.

Simply put, dynamic programming is an optimization technique used to solve problems. This technique chunks the work into tiny pieces so that the same work is being performed over and over again. You may opt to use dynamic programming techniques in a coding interview or throughout your programming career.

Dynamic programming caches values so that you don’t have to re-compute operations. This allows you to compute every value just once.

Great examples of problems you can solve with dynamic programming:

  • Calculating the Fibonacci sequence.

  • Calculating the amount of change you need to make up a dollar amount. For example, 32 cents USD is one quarter, one nickel, and two pennies.

  • Calculating the number of ways you can add or subtract an array of values to reach a target number.

  • Calculating the optimum combination of items you can include in a knapsack by the knapsack’s weight capacity.

Dynamic programming isn’t best for all problems. In many instances, dynamic programming just can’t help us in the improvement of the runtime of a problem. If your program isn’t performing repeated work, no amount of caching will make any difference.

If you’re very new to the concept of dynamic programming or have never even heard of it before, don't worry. All of these books on dynamic programming explain the idea in the simplest terms.

Overview of the Criteria For the Best Books on Dynamic Programming

Another problem you can solve using dynamic programming: Calculate the optimum combination of items you can include in a knapsack by the knapsack’s weight capacity.

Another problem you can solve using dynamic programming: Calculate the optimum combination of items you can include in a knapsack by the knapsack’s weight capacity.

Not all dynamic programming books are made equal. The best dynamic programming books available on the market do at least one of the following:

  • Use clear and precise language

  • Thoroughly explain the most important concepts

  • Contain practice problems and solutions

  • Structure themselves in such a way that self-taught programmers do not get left behind

  • Catch and hold the attention of readers

You’ll find many books out there that either focuses exclusively on dynamic programming or touches on the topic of dynamic programming in passing.

At Books on Code, we focus on the joy of reading. In my article How to Read Programming Books, I make a case that studying technical books should not be a miserable experience. Text books should always be doing as much work for you to digest and present the information in a way that you can best absorb it.

But dynamic programming is a heavy topic and not very sexy or marketable, so unfortunately, most books are dense and difficult to read. In the following list, I did my best to include books that are well-structured and informative.

Top 5 Books on Dynamic Programming

The Fibonacci sequence, which is a numerical pattern found in nature, such as in the number of petals on a flower, can be calculated using dynamic programming.

The Fibonacci sequence, which is a numerical pattern found in nature, such as in the number of petals on a flower, can be calculated using dynamic programming.

We’ve made it to the list!

See the following top 5 books on dynamic programming.

Book 1: Dynamic Programming and Optimal Control, Vol. I, 4th Edition

Dynamic Programming and Optimal Control by Dimitri Bertsekas prides itself on containing special features that allow it to stand out amongst the sea of introductory textbooks on dynamic programming. It touches and presents the following topics very clearly:

  • Deterministic control problems

  • Stochastic control problems

  • Pontryagin’s Minimum Principle

Also, it dedicates a full chapter to sub-optimal control and related techniques, such as:

  • Open-loop feedback controls

  • Limited look-ahead policies

  • Rollout algorithms

  • Model predictive control

As you can see, the book’s coverage is super complete. This makes it easy for me to recommend this book to you, regardless of whether you are a student in a graduate course on dynamic programming or self-learner.

Those who work as mathematicians, control theorists, and all those working with systems and control theory may find this book quite useful. Also, you’ll be glad to know that the material is clear and concise.

Book 2: Decision Theory: An Introduction to Dynamic Programming and Sequential Decisions

John Bather's Decision Theory: An Introduction to Dynamic Programming and Sequential Decisions does not exaggerate its title. It is an introductory book that focuses significantly on the basics of dynamic programming.

You may absorb more information when doing rather than merely reading. The teaching style of this book reflects this. The book provides many practice problems with explanations of all the techniques required to solve the problems.

As a bonus, the author's fluent style does an excellent job of igniting an avid interest in the subject. Listed below are some of the highlights of the textbook.

  • Tailored to the needs of learners of decision theory and optimization theory

  • Written in a conversational style with many applications and examples

  • Provides coverage of deterministic models: scheduling, convexity, maximizing utilities, directed networks, critical path analysis, and shortest paths

  • Provides coverage of stochastic models: optimal stopping problems, stochastic dynamic problems, and other special topics

  • Provides coverage of advanced topics: minimizing expected costs, policy improvements, problems with unknown statistical parameters, and Markov decision processes

  • Contains practical exercises along with hints and explanations

Although the book is aimed primarily at students of statistics and mathematics, the content also appeals significantly to engineering students, science students, and those working in the fields of optimization and operations research.

Book 3: Dynamic Programming for Coding Interviews: A Bottom-Up Approach to Problem Solving 

Coding interviews test your ability to not only program but also to think critically. Kamal Rawat’s Dynamic Programming for Coding Interviews: A Bottom-Up Approach to Problem Solving may be helpful for you if you’re hoping to ace your upcoming coding interview. 

In fact, the first few pages of the book include a handy reference entitled “How to Read This Book.” It basically comes in the form of if-else statements that guide you to the chapters that you should focus on, depending on your situation.

Even though you may not have a coding interview coming up, consider spending some time reading this book.

Sadly, most algorithm books only dedicate one chapter to dynamic programming. That chapter also discusses its related concepts, such as optimal substructure and overlapping-sub problems. But, those books tend to lack complex examples showcasing dynamic programming in action.

Dynamic Programming for Coding Interviews takes a different approach. This book dedicates one chapter per concept under dynamic programming. While discussing the ideas, the author provides straightforward examples. This allows you to maintain focus on the chapter's concept.

Once the concept is clear to you, the author then shifts focus to complex problem-solving.

Book 4: Algorithms Illuminated (Part 3): Greedy Algorithms and Dynamic Programming

Tim Roughgarden describes his Algorithms Illuminated (Part 3): Greedy Algorithms and Dynamic Programming book as an “accessible, no-nonsense, and programming language-agnostic introduction to algorithms.” 

The book includes hints and solutions for all quizzes and problems in the book. Also, the book provides links to supplemental Youtube videos by the author that accompany each chapter.

This book covers the following topics under greedy algorithms:

  • Scheduling

  • Minimum spanning trees

  • Clustering

  • Huffman codes

This book covers the following dynamic programming topics:

  • Knapsack

  • Sequence alignment

  • Shortest paths

  • Optimal search trees

Book 5: Algorithm Design Techniques: Recursion, Backtracking, Greedy, Divide and Conquer, and Dynamic Programming

Narasimha Karumanchi’s Algorithm Design Techniques is a detailed and easy-to-read guide that teaches you how to apply common algorithms to practical problems that coders face daily.

The following are a few things that make this book stand out:

  • Enumeration of the many possible solutions for a given problem

  • Performance trade-offs between algorithms

  • Example interview questions covering algorithms and data structures

  • Clear discussion of concepts

  • Python-based code samples

Final Thoughts

Don’t give up on dynamic programming! Yes, these algorithms may seem and feel frustrating at first. But with a book by your side, learning may become a little easier.

After some time spent reading any of the books listed above, along with some practice, writing dynamic programs will come to you more naturally. I hope you've found this list helpful in making your learning journey more enjoyable.

If you enjoyed this article, be sure to check out my free email course on reading faster and better.

If are interested in also learning all of your computer science fundamentals in one place, I cannot recommend Coursera’s Fundamentals of Computing by Rice University highly enough. The courses cover “much of the material that first-year Computer Science students take at Rice University.” And being honest — I got far more from this than I did my local university curriculum.

Looking for more recommendations on algorithms books? Well, I have just the article for you. Check out these top books on algorithms, and I will see you over there. 👋😊

 

Miranda Limonczenko

Miranda is the founder of Books on Code, with a mission to bring book-lover culture to programmers. Learn more by checking out Miranda on LinkedIn.

http://booksoncode.com
Previous
Previous

Clean Code Review: Top 7 Principles You Must Know

Next
Next

The 5 Best Books on Algorithms for Mastering the Code Interview