Dynamic Programming
It is a technique for solving a complex problem by first breaking into a collection of simpler
subproblems, solving each subproblem just once, and then storing their solutions to avoid
repetitive computations.
Use of dynamic programming:
Used to solve optimization problems Commented [RK1]: Optimization problems mean that
The dynamic programming guarantees to find the optimal solution of a problem if the when we are trying to find out the minimum or the maximum
solution/value of a problem.
solution exists.
Example:
Fibonacci sequence (A sequence in which the sum of two numbers is the third number in the
sequence)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
The numbers in the above series are not randomly calculated. Mathematically, we could write
each of the terms using the below formula:
F(n) = F(n-1) + F(n-2),
With the base values F(0) = 0, and F(1) = 1. To calculate the other numbers, we follow the
above relationship. For example, F(2) is the sum f(0) and f(1), which is equal to 1.
How can we calculate F(20)?
The F(20) term will be calculated using the nth formula of the Fibonacci series. The below
figure shows that how F(20) is calculated.
As we can observe in the above figure that F(20)
is calculated as the sum of F(19) and F(18). In the
dynamic programming approach, we try to divide
the problem into the similar subproblems. We are
following this approach in the above case where
F(20) into the similar subproblems, i.e., F(19)
and F(18). If we recap the definition of dynamic
programming that it says the similar subproblem
should not be computed more than once. Still, in
the above case, the subproblem is calculated
twice. In the above example, F(18) is calculated
two times; similarly, F(17) is also calculated
twice. However, this technique is quite useful as it solves the similar subproblems, but we need
to be cautious while storing the results because we are not particular about storing the result
that we have computed once, then it can lead to a wastage of resources.
The solution to the above problem is to save the computed results in an array. First, we calculate
F(16) and F(17) and save their values in an array. The F(18) is calculated by summing the
values of F(17) and F(16), which are already saved in an array. The computed value of F(18)
is saved in an array. The value of F(19) is calculated using the sum of F(18), and F(17), and
their values are already saved in an array. The computed value of F(19) is stored in an array.
The value of F(20) can be calculated by adding the values of F(19) and F(18), and the values
of both F(19) and F(18) are stored in an array. The final computed value of F(20) is stored in
an array.
Thus the problem statement is broken down into subproblems (n-1) AND (n-2), which gives
the optimal result, the next number in the sequence. Hence, it is a good example of dynamic
programming.
The main contrast between divide and conquer and dynamic programming is in DP, there can
be overlapping subproblems, but in the case of D and C, the subproblems are independent.
Dynamic Programming can’t solve all problems:
Dynamic programming cannot solve all the problems. There are several algorithms that
can be solved using greedy and divide and conquer techniques.
The difference between recursion and DP recursion is memoization in DP. If the
subproblem does not require memorization, in any case, DP cannot solve that problem.
Problems solved by the dynamic programming
The dynamic programming is applicable that are having properties such as:
Those problems that are having overlapping subproblems and optimal substructures.
How does the dynamic programming approach work?
The following are the steps that the dynamic programming follows:
o It breaks down the complex problem into simpler subproblems.
o It finds the optimal solution to these sub-problems.
o It stores the results of subproblems (memoization). The process of storing the results of
subproblems is known as memorization.
o It reuses them so that same sub-problem is calculated more than once.
o Finally, calculate the result of the complex problem.
Major components in Dynamic programming: The Following are components of dynamic
programming:
1. Recursion - To solve the problems recursively.
2. Memoization – To store the precomputation of subproblems to use further.
DP = RECURSION + MEMOIZATION
Properties of dynamic programming strategy
There are two strategies that show whether a given problem can be done with DP or not are:
1. Overlapping subproblems - A recursive solution that contains a small recursive
solution for subproblems.
2. Optimal substructure - An optimized solution to a problem that has optimal
subproblems.
Approaches of dynamic programming: Following are the basic approaches of DP -
1. Top-Down Approach: In this approach, the problem is broken into subproblems, and
the result at each sub problem is remembered. When a result at subproblem is needed
again further, it is first checked in the memory stage and then used.
2. Bottom-Up Approach: This approach follows the idea of computing first and moves
backward. It is done to avoid the process of recursion. The smaller inputs at each step
in the bottom-up approach contribute to form larger ones.
Examples of DP:
1. 0-1 Knapsack problem
2. Traveling salesman problem
3. Chain Matrix multiplication
4. String algorithms – Longest common subsequence, Longest increasing sequence etc.
5. Optimized graph algorithms and many more.
6.
Divide and Conquer Method vs Dynamic Programming
Divide and Conquer Method Dynamic Programming
Basic
[Link] (involves) three steps at each level of [Link]
dealsIdea involves problems by
the sequence of four steps:
Breaks problem into independent
recursion: breaking them into
o Characterize the structure of optimal
Divide the problemand
subproblems into asolves
number of subproblems.
them solutions.
overlapping
Conquer the
separately. subproblems by solving them o Recursively defines
subproblems the values of
and storing
recursively. optimal solutions.
results
CombineSubproblems
the solution to the subproblems into the o Compute the value of optimal
Subproblems overlap
solution for original subproblems. solutions in a Bottom-up minimum.
Subproblems are (same problem solved
o Construct an Optimal Solution from
independent (no multiple times)
computed information.
repetition)
Uses memoization (top-down) or
[Link]: Uses recursion to divide and
It is Recursive. 2. It istabulation
non Recursive.
(bottom-up)
combine and memoization
3. It does
Does notmore work
store on subproblems
results andusage)
(less memory hence has 3. It Stores
solves intermediate results (uses extra
subproblems only once and then
memory)
more time consumption. stores in the table.
May recompute same subproblems (less More efficient when subproblems
[Link]
It is a top-down approach.
in such cases)
4. Itrepeat
is a Bottom-up approach.
(avoids recomputation)
5. Merge
In this Sort,
subproblems are Binary
Quick Sort, independent
Searchof each 5. In thisFibonacci
subproblems areMatrix
(DP), interdependent.
Chain
other. Multiplication, Knapsack
Time Complexity
6. Depends
For example: Merge Sort & Binary Search etc.
on recurrence (can be higher
[Link]
For example: Matrix
optimized Multiplication.
(polynomial time)
due to repetition)