Introduction

Dynamic Programming (DP) requires:
- A solid understanding of recursion
- A basic understanding of what greedy algorithms are
- A general knowledge such as big O and hash tables
DP problems usually have the following characteristics:
- It can be broken down into "overlapping subproblems" - smaller versions of the original problem that are re-used multiple times
- It has an "optimal substructure" - an optimal solution can be formed from optimal solutions to the overlapping subproblems of the original problem
DP is a powerful because:
- It break a complex problem into manageable subproblems
- It avoids unnecessary recalculation of overlapping subproblems
- It uses the results of those subproblems to solve the initial complex problem
There are two ways to implement a DP algorithm:
- Bottom-up, a.k.a. tabulation. It uses iteration and array
- Top-down, a.k.a. memoization. It uses recursion and hash map
There a framework for DP problems and it consists of three parts:
- A function computes the answer of given state (top-town) / A data structure contains the answer of given state (bottom-up)
- A recurrence relation to transition between states
- Base cases for termination
The number of state variables decides a dimension of a DP problem. However, the framework works regardless of the number of dimensions

Contents