# Dynamic Programming Basics

Difficulty Level Easy
Dynamic Programming Theory

In Dynamic Programming basics, we will cover the basics of DP and its differences from the Greedy method, Divide and Conquer and Recursion.

Dynamic programming is an approach just like recursion and divide and conquer. It divides the problem into subproblems. But instead of solving these subproblems independently like divide and conquer and recursion, it uses the results of previous subproblems for similar computations also known as an overlapping problem.

It is used for the optimization of programs. As it uses the previously computed results, using its exponential time complexity can be reduced to polynomial. For instance – The time complexity of the recursive solution of Ugly Numbers is exponential and of DP solution is linear.

## Some basic problems of DP

• Ugly numbers problem
• Coin change
• Fibonacci numbers
• Bell numbers problem
• Tower of Hanoi
• Bell numbers
• Knapsack problem

## Dynamic Programming (DP) vs Greedy Method

In DP each step evaluates the solution considering the current as well as previous solutions to obtain the optimal solution. However, in the greedy algorithm, we select the best option considering only the current situation.

Although greedy methods are generally faster than DP and are also memory efficient as it does not store previously computed values for future use, it does not give assurance of an optimal solution.

## Dynamic Programming (DP) vs Divide & Conquer Method

In divide and conquer we divide a problem into subproblems and solve each subproblem independently. However, in DP rather than solving problems independently, we use the previously obtained results for new computations. In other words, we can say Divide and Conquer + Memoization = top-down dynamic approach.