In this article, we explore how Dynamic Programming is applied on Mathematical Problems with examples of such problem statements.
Categories of Mathematical Problems where Dynamic Programming is applicable are:
- Problems involving combinatorics and permutation
- Finding a sub-sequence with a property
- Generating a sequence
- Finding subsets with a property
Problems involving combinatorics and permutation
Permutation and Combination is the core of Mathematical problems where we need to find the total number of possibilities.
Permutation P(n, k) is defined as the number of combinations of getting K elements in order from a set of N elements. It equates to the following:
P(n,k) = n.(n-1).(n-2)...(n-k+1) = n!/(n-k)!
As Dynamic Programming requires, Permutation depends on smaller values of permutation:
P(n,k) = P(n-1, k) + k * P(n-1, k-1)
Similarly, Combination C(n, k) is defined as the number of combinations of getting K elements (no order) from a set of N elements. It equates to the following:
C(n,k) = n! / [ k! (n-k)! ]
As Combination is a special case of Permutation, it follows the DP structure.
C(n, k) * k! = P(n, k)
In practice problems, you will understand how Dynamic Programming exploits this basic feature to solve several Mathematical Problems efficiently.
Finding a sub-sequence with a property
Examples of problems where we need to find a sub-sequence with a property are:
- Longest Increasing Subsequence
- Longest Decreasing Subsequence
- Longest Common Increasing Subsequence
In a set of N elements, there are 2^N subsequences. This is an exponential size so brute force is not a feasible solution.
The only way to identify a specific subsequence with a given property is to:
- Identify sub-problems that follow DP structure
- Apply DP to find the subsequence in polynomial time
The key is to think if you have the answer of the first N-1 elements, then how can you use the answer to find the answer of the complete set of N elements.
Generating a sequence
Examples of problems where we need to generate a sequence are:
- Newman Conway Sequence
- n-th Fibonacci number
These are case where:
- the N-th element in a sequence is derived using previous elements of the sequence
- there is no direct formula to compute N-th element OR a direct formula is computationally expensive
In such cases, Dynamic Programming can find a relatively efficient approach to generate multiple elements of the sequence at once.
Finding subsets with a property
Example of problems where we need to find subsets with a property are:
- Find if a Subset with sum divisible by m exist
This is similar to the category "Finding a sub-sequence with a property".
If you look carefully, these are a kind of optimization problems. These are several possibilities (generally, exponential) and we need to traverse through all possibilities to find the one which is our answer.
Dynamic Programming starts with smaller values and:
- Either traverses significantly less possibilities
- Checks only combinations that follow one another and eventually, reaches the answer
- Traverses through possibilities in a structured way
On going through multiple examples in this book, you will understand how Dynamic Programming is applied in Mathematical Problems.
With this article at OpenGenus, you must have a strong idea of applying Dynamic Programming on Mathematical Problems.