# Dynamic Programming Problems

0
43

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.

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 proﬁt you make when you ﬁnish the job, what is the maximum proﬁt 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 ﬁnished, we focus on making the maximum proﬁt. 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 ﬁnishing time and proﬁt. After a few iterations, we can ﬁnd out if we perform Job-A and Job-E, we can get the maximum proﬁt of 17. Now how to ﬁnd this out using an algorithm?

The ﬁrst thing we do is sort the jobs by their ﬁnishing time in non-decreasing order. Why do we do this? It’s because if we select a job that takes less time to ﬁnish, 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 proﬁt of performing the jobs. Don’t get it? Wait and watch. We’ll initialize the values of the array with the proﬁt of each jobs. That means, Acc_Prof[i] will at ﬁrst hold the proﬁt 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 ﬁnish 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] + Proﬁt[i] > Acc_Prof[i]. If this is the case, we will update Acc_Prof[i] = Acc_Prof[j] + Proﬁt[i]. That is:

Here Acc_Prof[j] + Proﬁt[i] represents the accumulated proﬁt 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 proﬁt we can make by picking these two jobs is: Acc_Prof[j] + Proﬁt[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 proﬁt 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 proﬁt 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 ﬁnally look like:

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

If we iterate through the array Acc_Prof, we can ﬁnd out the maximum proﬁt 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 ﬁnd out which jobs were performed to get the maximum proﬁt, we need to traverse the array in reverse order and if the Acc_Prof matches the maxProﬁt, we will push the name of the job in a stack and subtract Proﬁt of that job from maxProﬁt. We will do this until our maxProﬁt > 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 proﬁt, we can only ﬁnd one job schedule via this procedure.

## Longest Common Subsequence

If we are given with the two strings we have to ﬁnd 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

Overlapping Sub-problems

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

Implementation

Time Complexity: O(n).

## Longest Common Substring

Given 2 string `str1` and `str2` we have to ﬁnd 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

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