#### Overview of this book

Learning about data structures and algorithms gives you a better insight on how to solve common programming problems. Most of the problems faced everyday by programmers have been solved, tried, and tested. By knowing how these solutions work, you can ensure that you choose the right tool when you face these problems. This book teaches you tools that you can use to build efficient applications. It starts with an introduction to algorithms and big O notation, later explains bubble, merge, quicksort, and other popular programming patterns. You’ll also learn about data structures such as binary trees, hash tables, and graphs. The book progresses to advanced concepts, such as algorithm design paradigms and graph theory. By the end of the book, you will know how to correctly implement common algorithms and data structures within your applications.
Title Page
Packt Upsell
Contributors
Preface
Free Chapter
Algorithms and Complexities
Sorting Algorithms and Fundamental Data Structures
Hash Tables and Binary Search Trees
String Matching Algorithms
Graphs, Prime Numbers, and Complexity Classes
Other Books You May Enjoy
Index

## Understanding Dynamic Programming

After greedy and divide and conquer, we will turn our attention to dynamic programming. Dynamic programming is an algorithm design paradigm that also attempts to solve optimization problems by combining solutions with subproblems. Unlike divide and conquer, subproblems need to exhibit optimal substructure for dynamic programming to be applicable.

### Elements of a Dynamic Programming Problem

There are two key ingredients that an optimization problem must have for dynamic programming to be applicable: optimal substructure and overlapping subproblems.

#### Optimal Substructure

Optimal substructure is something we already covered when we introduced greedy algorithms. Recall that a problem exhibits optimal substructure, if an optimal solution to the problem contains within it, the optimal solutions to the sub-problems. There's a common pattern when trying to discover optimal substructure for a problem that can be explained as follows:

• Show that a solution to the problem consists...