Dynamic Programming Beginner’s Tutorial
Dynamic programming is a method for solving a complex problem by breaking it down into simpler subproblems, solving each of those subproblems just once, and storing their solutions – in an array(usually).
Now, every time the same sub-problem occurs, instead of recomputing its solution, the previously calculated solutions are used, thereby saving computation time at the expense of storage space.
Dynamic programming can be implemented in two ways –
- Memoization
- Tabulation
Memoization – Memoization uses the top-down technique to solve the problem i.e. it begin with original problem then breaks it into sub-problems and solve these sub-problems in the same way.
In this approach, you assume that you have already computed all subproblems. You typically perform a recursive call (or some iterative equivalent) from the main problem. You ensure that the recursive call never recomputes a subproblem because you cache the results, and thus duplicate sub-problems are not recomputed.
Tabulation – Tabulation is the typical Dynamic Programming approach. Tabulation uses the bottom-up approach to solve the problem, i.e., by solving all related sub-problems first, typically by storing the results in an array. Based on the results stored in the array, the solution to the “top” / original problem is then computed.
Memoization and tabulation are both storage techniques applied to avoid recomputation of a subproblem
Example – Consider a program to generate Nth fibonacci number
Fib(n)=Fib(n-1)+Fib(n-2)
Solution 1 – using top-down approach without Dynamic Programming
int Fib(int n)
{if(n<=1)
{return n;
}else{return (fibonacci(n-1)+fibonacci(n-2));
}}
Solution 2 – using top-down approach with Memoization (Dynamic Programming)
int memoize[];
//method to initialize memoize array to -1void initialize()
{...
}int Fib(int n)
{if(memoize[n]==-1)
{//means the solution is not yet calculatedif(n<=1)
{memoize[n]=1;
}else{memoize[n]=Fib[n-1]+Fib[n-2];
}}return memoize[n];
}
Solution 3 – Bottom up Dynamic Programming
int table[N];
void setup_fib()
{table[0] = 1;
table[1] = 1;
for (int i = 2; i < N; i++)
table[i] = table[i-1] + table[i-2];
}int Fib(int x)
{return table[x];
}
The idea behind dynamic programming, In general, is to solve a given problem, by solving different parts of the problem (subproblems), then using the cached solutions of the subproblems to reach an overall solution.
APPLICABILITY OF DYNAMIC PROGRAMMING-
The problems that can be solved by using Dynamic Programming has the following two main properties-
- Overlapping sub-problems
- Optimal Substructure
1) Overlapping Subproblems:
Overlapping subproblems is a property in which a problem can be broken down into subproblems which are used multiple times.
Dynamic Programming is mainly used when solutions of same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a array so that these don’t have to recomputed. So Dynamic Programming is not useful when there are no overlapping subproblems because there is no point storing the solutions if they are not needed again.
2) Optimal substructure
Optimal substructure is a property in which an optimal solution of the original problem can be constructed efficiently from the optimal solutions of its sub-problems.
If a given problem obey both these properties, then the problem can be solved by using Dynamic Programming.
Steps to follow for solving a DP problem –
- Express a solution mathematically
- Express a solution recursively
- Either develop a bottom up algorithm or top-down memoized algorithm
Here’s the List of Dynamic Programming Problems and their Solutions
