Last updated on September 4th, 2023 at 09:40 pm

Here, We will discuss about Dynamic Programming, their strategy, properties and approaches like memoization and tabulation** **and their applications.

**What is Dynamic Programming?**

**Dynamic Programming** is a powerful technique to solve a complicated problem by breaking it down into simpler subproblems.

The idea of dynamic programming is to avoid making redundant method calls.

*In Divide and Conquer*, sub-problems are independent. While *In Dynamic Programming*, sub-problems are dependent.

Majority of the Dynamic Programming problems can be divided into two types:

- Optimization problems
- Combinatorial problems

Some famous Dynamic Programming algorithms are:

*Unix diff*for comparing two files*Bellman-Ford*for shortest path routing in networks*TeX*the ancestor of LaTeX*WASP*– Winning and Score predictor

**Dynamic Programming strategy**

The major components of Dynamic Programming are:

**Recursion:**Solves subproblems recursively.**Memoization:**Stores already computed values in the table (*Memoization means caching*)

Dynamic Programming ≈ Recursion + Memoization (i.e. reuse)

Dynamic Programming ≈ controlled brute force

*By using memoization,* dynamic programming reduces the exponential complexity to polynomial complexity (O(n^{2}), O(n^{3}), etc) for many problems.

**Properties of Dynamic Programming**

The two dynamic programming properties which can tell whether it can solve the given problem or not are:

**Optimal substructure:**an optimal solution to a problem contains optimal solutions to sub-problems.**Overlapping subproblems**: a recursive solution contains a small number of distinct subproblems repeated many times.

Dynamic Programming results in an efficient algorithm, if the following conditions hold:

- The optimal solution can be produced by combining optimal solutions of subproblems.
- The optimal solution of each subproblems can be produced by combining optimal solutions of sub-subproblems, etc.
- The total number of subproblems arising recursively is polynomial.

**Dynamic Programming Approaches**

There are typically two approaches in Dynamic Programming to reach a solution:

**Memoization****(Top-Down)**(*Memoization means caching).***Tabulation (Bottom-Up)**

**Memoization (Top-Down Approach)**

```
#Fibonacci Series in PYTHON
def fibonacci(n, store):
#base condition for 1st and 2nd number
if(n == 1):
return 0
if(n == 2):
return 1
#recursive computation of nth fibonacci number
if(store[n] == -1):
return fibonacci(n-1) + fibonacci(n-2)
else:
return store[n]
n=7
store = [-1 for i in range(n+1)]
print("The nth number is : ", fibonacci(n, store))
```

**Tabulation (Bottom-Up Approach)**

```
#Fibonacci Series in PYTHON
def fibonacci(n, store):
#initializing store
#assuming store begins from 1
store = [-1 for i in range(n+1)]
#using base condition to initialize some values
store[1] = 0
store[2] = 1
#using the relation derived from recursive calls to compute store values
for i in range(3, n+1):
store[i] = store[i-1] + store[i-2]
#fibonacci(n) ---> store[n]
return store[n]
n = 7
store = [-1 for i in range(n+1)]
print("The nth number is : ", fibonacci(n, store))
```

**Applications of Dynamic Programming**

- String Algorithms – Longest Common subsequence, Longest increasing subsequence, Longest common substring, edit distance.
- Bellman-Ford algorithm for finding the shortest distance in a graph.
- Floyd algorithm for finding all pairs shortest path algorithm etc
- Chain matrix multiplication
- Subset Sum
- 0/1 Knapsack
- Travelling salesman problems and many more.

### Related:

*Want to Contribute*:-

If you like “**To The Innovation**” and want to contribute, you can mail your articles to 📧 **contribute@totheinnovation.com**. See your articles on the main page and help other coders.😎