**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**

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public class EditDistance { public static void main(String[] args) { // TODO Auto-generated method stub String str1 = "march"; String str2 = "cart"; EditDistance ed = new EditDistance(); System.out.println(ed.getMinConversions(str1, str2)); } public int getMinConversions(String str1, String str2) { int dp[][] = new int[str1.length() + 1][str2.length() + 1]; for (int i = 0; i <= str1.length(); i++) { for (int j = 0; j <= str2.length(); j++) { if (i == 0) dp[i][j] = j; else if (j == 0) dp[i][j] = i; else if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1]; else { dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])); } } } return dp[str1.length()][str2.length()]; } } |

**Output**

0 1 2 |
3 |

## 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:

0 1 2 3 4 5 6 |
if Job[j].finish_time <= Job[i].start_time if Acc_Prof[j] + Profit[i] > Acc_Prof[i] Acc_Prof[i] = Acc_Prof[j] + Profit[i] endif endif |

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:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Procedure WeightedJobScheduling(Job) sort Job according to finish time in non-decreasing order for i -> 2 to n for j -> 1 to i-1 if Job[j].finish_time <= Job[i].start_time if Acc_Prof[j] + Profit[i] > Acc_Prof[i] Acc_Prof[i] = Acc_Prof[j] + Profit[i] endif endif endfor endfor maxProfit = 0 for i -> 1 to n if maxProfit < Acc_Prof[i] maxProfit = Acc_Prof[i] return maxProfit |

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:

0 1 2 3 4 5 6 7 8 9 |
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit): S = stack() for i -> n down to 0 and maxProfit > 0 if maxProfit is equal to Acc_Prof[i] S.push(Job[i].name maxProfit = maxProfit - Job[i].profit endif endfor |

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**

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
public class LCS { public static void main(String[] args) { // TODO Auto-generated method stub String str1 = "AGGTAB"; String str2 = "GXTXAYB"; LCS obj = new LCS(); System.out.println(obj.lcs(str1, str2, str1.length(), str2.length())); System.out.println(obj.lcs2(str1, str2)); } //Recursive function public int lcs(String str1, String str2, int m, int n) { if (m == 0 || n == 0) return 0; if (str1.charAt(m - 1) == str2.charAt(n - 1)) return 1 + lcs(str1, str2, m - 1, n - 1); else return Math.max(lcs(str1, str2, m - 1, n), lcs(str1, str2, m, n - 1)); } //Iterative function public int lcs2(String str1, String str2) { int lcs[][] = new int[str1.length() + 1][str2.length() + 1]; for (int i = 0; i <= str1.length(); i++) { for (int j = 0; j <= str2.length(); j++) { if (i == 0 || j == 0) { lcs[i][j] = 0; } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) { lcs[i][j] = 1 + lcs[i - 1][j - 1]; } else { lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]); } } } return lcs[str1.length()][str2.length()]; } } |

**Output**

0 1 2 |
4 |

## 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**

0 1 2 3 4 5 6 7 8 9 |
public int fib(int n){ int f[] = new int[n+1]; f[0]=0;f[1]=1; for(int i=2;i<=n;i++){ f[i]=f[i-1]+f[i-2]; } return f[n]; } |

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**

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public int getLongestCommonSubstring(String str1, String str2) { int arr[][] = new int[str2.length() + 1][str1.length() + 1]; int max = Integer.MIN_VALUE; for (int i = 1; i <= str2.length(); i++) { for (int j = 1; j <= str1.length(); j++) { if (str1.charAt(j - 1) == str2.charAt(i - 1)) { arr[i][j] = arr[i - 1][j - 1] + 1; if (arr[i][j] > max) max = arr[i][j]; } else arr[i][j] = 0; } } return max; } |

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