Dynamic Programming Problems

0
43
dynamic programing problems tutorial
dynamic programing problems tutorial

Dynamic programming is a widely used concept and its often used for optimization. It refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner usually a bottom-up approach. There are two key attributes that a problem must have in order for dynamic programming to be applicable “Optimal substructure” and “Overlapping sub-problems”. To achieve its optimization, dynamic programming uses a concept called memoization.

You can learn more algos here: https://free4dev.com/category/algorithms/

Some common dynamic programming problems:

  • edit distance problem
  • weighted job ccheduling
  • Fibonacci number
  • longest common sub-sequence
  • longest common sub-string

Edit Distance algorithm

The problem statement is like if we are given two string str1 and str2 then how many minimum number of operations can be performed on the str1 that it gets converted to str2.

Implementation in Java

Output

Weighted Job Scheduling Algorithm

Weighted Job Scheduling Algorithm can also be denoted as Weighted Activity Selection Algorithm.

The problem is, given certain jobs with their start time and end time, and a profit you make when you finish the job, what is the maximum profit you can make given no two jobs can be executed in parallel?

This one looks like Activity Selection using Greedy Algorithm, but there’s an added twist. That is, instead of maximizing the number of jobs finished, we focus on making the maximum profit. The number of jobs performed doesn’t matter here.

Let’s look at an example:

The jobs are denoted with a name, their start and finishing time and profit. After a few iterations, we can find out if we perform Job-A and Job-E, we can get the maximum profit of 17. Now how to find this out using an algorithm?

The first thing we do is sort the jobs by their finishing time in non-decreasing order. Why do we do this? It’s because if we select a job that takes less time to finish, then we leave the most amount of time for choosing other jobs. We have:

We’ll have an additional temporary array Acc_Prof of size n (Here, n denotes the total number of jobs). This will contain the maximum accumulated profit of performing the jobs. Don’t get it? Wait and watch. We’ll initialize the values of the array with the profit of each jobs. That means, Acc_Prof[i] will at first hold the profit of performing i-th job.

Now let’s denote position 2 with i, and position 1 will be denoted with j. Our strategy will be to iterate j from 1 to i-1 and after each iteration, we will increment i by 1, until i becomes n+1.

We check if Job[i] and Job[j] overlap, that is, if the finish time of Job[j] is greater than Job[i]‘s start time, then these two jobs can’t be done together. However, if they don’t overlap, we’ll check if Acc_Prof[j] + Profit[i] > Acc_Prof[i]. If this is the case, we will update Acc_Prof[i] = Acc_Prof[j] + Profit[i]. That is:

Here Acc_Prof[j] + Profit[i] represents the accumulated profit of doing these two jobs toegther. Let’s check it for our example:

Here Job[j] overlaps with Job[i]. So these to can’t be done together. Since our j is equal to i-1, we increment the value of i to i+1 that is 3. And we make j = 1.

Now Job[j] and Job[i] don’t overlap. The total amount of profit we can make by picking these two jobs is: Acc_Prof[j] + Profit[i] = 5 + 5 = 10 which is greater than Acc_Prof[i]. So we update Acc_Prof[i] = 10. We also increment j by 1. We get,

Here, Job[j] overlaps with Job[i] and j is also equal to i-1. So we increment i by 1, and make j = 1. We get,

Now, Job[j] and Job[i] don’t overlap, we get the accumulated profit 5 + 4 = 9, which is greater than Acc_Prof[i]. We update Acc_Prof[i] = 9 and increment j by 1.

Again Job[j] and Job[i] don’t overlap. The accumulated profit is: 6 + 4 = 10, which is greater than Acc_Prof[i]. We again update Acc_Prof[i] = 10. We increment j by 1. We get:

If we continue this process, after iterating through the whole table using i, our table will finally look like:

* A few steps have been skipped to make the document shorter.

If we iterate through the array Acc_Prof, we can find out the maximum profit to be 17. The pseudo-code:

The complexity of populating the Acc_Prof array is O(n2). The array traversal takes O(n). So the total complexity of this algorithm is O(n2).

Now, If we want to find out which jobs were performed to get the maximum profit, we need to traverse the array in reverse order and if the Acc_Prof matches the maxProfit, we will push the name of the job in a stack and subtract Profit of that job from maxProfit. We will do this until our maxProfit > 0 or we reach the beginning point of the Acc_Prof array. The pseudo-code will look like:

The complexity of this procedure is: O(n).

One thing to remember, if there are multiple job schedules that can give us maximum profit, we can only find one job schedule via this procedure.

Longest Common Subsequence

If we are given with the two strings we have to find the longest common sub-sequence (LCS) present in both of them.

Example

LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.

LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

Implementation in Java

Output

Fibonacci Number

Bottom up approach for printing the nth Fibonacci number using Dynamic Programming.

Recursive Tree

Dynamic programming - Fibonacci number

Overlapping Sub-problems

Here fib(0), fib(1) and fib(3) are the overlapping sub-problems. fib(0) is getting repeated 3 times, fib(1) is getting repeated 5 times and fib(3) is getting repeated 2 times.

Implementation

Time Complexity: O(n).

Longest Common Substring

Given 2 string str1 and str2 we have to find the length of the longest common substring between them.

Examples

Input : X = “abcdxyz”, y = “xyzabcd” Output : 4
The longest common substring is “abcd” and is of length 4.
Input : X = “zxabcdezy”, y = “yzabcdezx” Output : 6
The longest common substring is “abcdez” and is of length 6.

Implementation in Java

Time Complexity: O(m*n).

Note: This modified text is an extract of the original Stack Overflow Documentation and released under CC BY-SA 3.0

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.