#### Overview of this book

C++ is a mature multi-paradigm programming language that enables you to write high-level code with a high degree of control over the hardware. Today, significant parts of software infrastructure, including databases, browsers, multimedia frameworks, and GUI toolkits, are written in C++. This book starts by introducing C++ data structures and how to store data using linked lists, arrays, stacks, and queues. In later chapters, the book explains the basic algorithm design paradigms, such as the greedy approach and the divide-and-conquer approach, which are used to solve a large variety of computational problems. Finally, you will learn the advanced technique of dynamic programming to develop optimized implementations of several algorithms discussed in the book. By the end of this book, you will have learned how to implement standard data structures and algorithms in efficient and scalable C++ 14 code.
Free Chapter
1. Lists, Stacks, and Queues
2. Trees, Heaps, and Graphs
3. Hash Tables and Bloom Filters
4. Divide and Conquer
5. Greedy Algorithms
6. Graph Algorithms I
7. Graph Algorithms II
8. Dynamic Programming I
9. Dynamic Programming II

## Memoization – The Top-Down Approach

No, this is not "memorization," though that would also describe this technique quite accurately. Using memoization, we can reformulate the top-down solution we described previously to make use of the optimal substructure property exhibited by the Fibonacci sequence. Our program logic will essentially be the same as it was before, only now, after having found the solution at every step, we will cache the results in an array, indexed according to the current value of n (in this problem, n represents the state or set of parameters defining the current recursive branch). At the very beginning of each function call, we will check to see whether we have a solution available in the cache for state F(n). If so, we will simply return the cached value:

const int UNKNOWN = -1;

const int MAX_SIZE = 100000;

vector<int> memo(MAX_SIZE, UNKNOWN);

int Fibonacci(int n)

{

if(n < 2)

{

...