# Dynamic Programming

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:

1. Optimization problems
2. 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:

1. Recursion: Solves subproblems recursively.
2. 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(n2), O(n3), 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:

1. Optimal substructure: an optimal solution to a problem contains optimal solutions to sub-problems.
2. 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:

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

### Dynamic Programming Approaches

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

1. Memoization (Top-Down) (Memoization means caching).
2. 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))```Code language: Python (python)```

#### 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 = 0
store = 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))```Code language: Python (python)```

### Applications of Dynamic Programming

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

#### Jump Game II LeetCode Solution

You are given a 0-indexed array of integers nums of length n. You are initially…

#### Wildcard Matching LeetCode Solution

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support…

#### Trapping Rain Water LeetCode Solution

Given n non-negative integers representing an elevation map where the width of each bar is…

#### Longest Valid Parentheses LeetCode Solution

Given a string containing just the characters ‘(‘ and ‘)’, return the length of the…

#### Climbing Stairs LeetCode Solution

You are climbing a staircase. It takes n steps to reach the top. Each time you can…

#### Regular Expression Matching LeetCode Solution

Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where ‘.’ Matches any…

### 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.😎

Scroll to Top