# 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)

```.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```#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.😎