# Dynamic Programming

## Introduction

Dynamics programming is a widely used concept and its often used for optimization. It refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner usually Bottom up approach. There are two key attributes that a problem must have in order for dynamic programming to be applicable “Optimal substructure” and “Overlapping sub-problems”.To achieve its optimization, Dynamics programming uses a concept called Memorization

## Remarks

Dynamic Programming is an improvement on Brute Force, see this example to understand how one can obtain a Dynamic Programming solution from Brute Force.

A Dynamic Programming Solution has 2 main requirements:

- Overlapping Problems
- Optimal Substructure

* Overlapping Subproblems* means that results of smaller versions of the problem are reused multiple times in order to arrive at the solution to the original problem

* Optimal Substructure* means that there is a method of calculating a problem from its subproblems.

A Dynamic Programming Solution has 2 main components, the * State* and the

**Transition**The * State* refers to a subproblem of the original problem.

The * Transition* is the method to solve a problem based on its subproblems

The time taken by a Dynamic Programming Solution can be calculated as `No. of States * Transition Time`

. Thus if a solution has `N^2`

states and the transition is `O(N)`

, then the solution would take roughly `O(N^3)`

time.