Dynamic Programming

Find Common SubString in two Strings

public class LongestCommonSubString {
 public int lcSubString(char[] first,char[] second){
  int max=0;
  int temp[][] = new int[first.length][second.length];
  for(int i=1;i<temp.length;i++){
   for(int j=1;j<temp[0].length;j++){
    if(first[i-1] == second[j-1])
     temp[i][j] =  temp[i-1][j-1] + 1;
        if(max < temp[i][j])
         max = temp[i][j];
   }
  }
  return max;
 }
 
 public static void main(String args[]) {
  String first = "OldSite:GeeksforGeeks.org";
  String second = "NewSite:GeeksQuiz.com";
  System.out.println(" ---  " + new LongestCommonSubString().lcSubString(first.toCharArray(), second.toCharArray()));
 }
}

Find the longest SubSequence(length) in a Suquence

public class LongestIncreasingSubSequence {
 public int lis(int[] arr){
 int max = 0;
 int[] ls = new int[arr.length];
 for(int i=0;i<arr.length;i++){
  ls[i] = 1;
 }
 for(int i=1;i<arr.length;i++){
  for(int j = 0;j<i;j++){
     if(arr[j]<arr[i] && (ls[j]+1)-ls[i]>0){
      ls[i] = ls[i] +1;
     }
  }
 }
 
 
 for(int i=0;i<ls.length;i++){
  if(ls[i] > max)
   max = ls[i];
 }
  return max;
 }
 
 public static void main(String args[]) {
  int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
  System.out.println(" Longest increasing seq. has length  "+new LongestIncreasingSubSequence().lis(arr));
 }
}

Edit Distance

public class EditDistance {
 private final int EDIT_COST = 1;
 public int minEdits(char[] ch1, char[] ch2) {
  int min = 0;
  int[][] temp = new int[ch1.length + 1][ch2.length + 1];
  for (int i = 0; i < temp.length; i++) {
   temp[i][0] = i;
  }
  for (int j = 0; j < temp[0].length; j++) {
   temp[0][j] = j;
  }
  for (int i = 1; i < ch1.length; i++)
   for (int j = 1; j < ch2.length; j++) {
    if (ch1[i] == ch2[j]) {
     temp[i][j] = temp[i - 1][j - 1];
    } else {
     temp[i][j] = min(temp[i - 1][j - 1] + 1, temp[i - 1][j]
       + EDIT_COST, temp[i][j - 1] + EDIT_COST);
    }
   }
  return min;
 }

 private int min(int a, int b, int c) {
  int temp = Math.min(a, b);
  return Math.min(temp, c);
 }

 public static void main(String args[]) {
  String str1 = "sunday";
  String str2 = "saturday";
  System.out.println(" Minimum edits needed are "
    + new EditDistance().minEdits(str1.toCharArray(),
      str2.toCharArray()));

 }

}

Example above explains the minimum number of edits required to change a string to another, where in the edits include the following operations:

Add

Remove

Edit/Modify

EDIT_Cost is the value associated with the cost for a single edit.