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(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:
- 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)
Code language: Python (python)
#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)
Code language: Python (python)
#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))
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.
Want to Contribute:-
If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 [email protected]. See your articles on the main page and help other coders.😎