What is Dynamic Programming...

Dynamic programming(DP) is the general and powerful method of solving some class of problems.It is often used for optimization.We break a complex problem into smaller sub problems and solve each of the individual sub problems at once and store the solution. When we suppose to solve a sub problem,we check whether it is already computed or not.if it is so,we just look its solution.

so,essentially  DP=sub problems+"reuse of computed results"

Memoization:

The technique of reusing the stored solutions of sub problems without recomputing them is known as 'Memoization'.

How to implement DP?

There are two approaches to implement DP.

1)Top down approach

2)Bottom up approach

Top-down approach:

Here, we divide the complex problem into number of sub problems.whenever we attempt to solve a new sub problem, we first check the table to see if it is already solved.if a solution has been recorded,we use it directly,otherwise we solve the sub problem and add its solution to the table.

Bottom-up approach:

In this case we try solving the sub problems first and use their solutions to build-on and arrive at solutions to bigger sub problems.

When to use Dp ?

DP has two properties.

1)Optimal substructures.

2) Overlapping sub problems

Optimal substructures:

A problem is said to have optimal substructure when there exists an optimal solution derived from optimal solutions of its sub problems.

Overlapping sub problems:

Overlapping sub problems is nothing but repetition of sub problems. 

So,whenever you feel the given problem has these properties,you can choose DP to solve it.

Time and Space complexities:

The time complexity of DP problems vary from problem to problem.However,we generally calculate time complexity for DP problems as 

T.C = no.of sub problems * time taken to solve each sub problem 

The space complexity for DP problems depends on the data structure that we use  to store the computed results of the sub problems.

Points to be noted:   

DP vs Recursion:

It seems to be that DP is quite similar to recursion.But,there is a significant difference between them.

Recursion helps just to breakdown the problems into sub problems.The sub problem may be computed more than once.

Whereas,in DP we store the result of the previous computation to avoid computing the same sub problem once again.

DP vs D&C:

If we say dividing the complex problems into sub problems most of us may think about divide and conquer So,I want to make it clear that D&C method is used to solve the non-overlapping sub problems,but in DP we deal with overlapping sub problems.