Longest palindrome Sub-sequence from the given String using Dynamic Programming

Longest palindrome Sub-sequence from the given String using Dynamic Programming

Longest palindrome Sub-sequence  

Write a program to find the longest sub-sequence palindrome from the given string by using dynamic programming. For example

Input String : ABCDQRDC

Longest sub-sequence palindrome: 5

•  So let's see how we will solve and find the longest subsequence palindrome using dynamic programming. 
• 
  
• Construct the solution matrix of size NxN where N is the length of given string. 
• We will calculate the size of each character sequence palindrome size and will the memorised in the solution matrix which will referred for the next incremental sequence.
• For example in above example all strings of 1 character will be palindrome size of 1. A, B, C, D, Q, R, D, C
• On next cycle it will add another character and makes 2 character string like 
• AB, BC, CD, DQ, QR, RD, DC and goes on like 
• ABC, BCD, CDQ, DQR, QRD, RDC etc.,
• Each sequences palindrome size will be stored in the solution array and finally returns the maximum size as output.

Now lets see simple Java code 

 public class LongestPalindromeSequence {

 public static void main(String[] args) {

  String str = "ABCDQRDC";

  LongestPalindromeSequence obj = new LongestPalindromeSequence();

  System.out.println("\nLength of Longest palindrome subsequence : " + obj.lps(str));

 }

 public int lps(String seq) {
  int n = seq.length();
  int j, k, i;
  int L[][] = new int[n][n];

  // Strings of 1 character will be palindrome size of 1 
  // starting with upper matrix and all single character falls diagonally and size will be 1
  for (j = 0; j < n; j++)
   L[j][j] = 1;

  for (i = 2; i <= n; i++) {
   for (j = 0; j < n - i + 1; j++) {

    k = j + i - 1;

    if (seq.charAt(j) == seq.charAt(k)) {
     L[j][k] = L[j + 1][k - 1] + 2;

    } else {
     L[j][k] = Math.max(L[j][k - 1], L[j + 1][k]);
    }
   }
  }

  /*System.out.println("Final solution Matrix :::: ");
  for (j = 0; j < n; j++) {
   System.out.print(seq.charAt(j) +" - ");
   for (k = 0; k < n; k++) {
    System.out.print(L[j][k] + "\t");
   }
   System.out.println();
  }*/
  return L[0][n - 1];
 }
}

OUTPUT:

Length of Longest palindrome subsequence : 5

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java  

The Longest Common Subsequence (LCS) problem is given with two strings like "ABAZDC" and "BACBAD". LCS is to find their longest common subsequence that appear left-to-right but not necessarily in a contiguous block in both the strings. Here we will see how to achieve Longest Common Subsequence (LCS) algorithm using Dynamic Programming using Java.

Example:
Str1 = "ABAZDC"
Str2 = "BACBAD"

Here the Longest Common Subsequence (LCS) size will be 4 and the Longest Common Subsequence (LCS) will "ABAD".

How to find Longest Common Subsequence (LCS)?

First we need to construct matrix of size str1 and str2 like matrix[str1.length][str2.matrix] as shown below

Whenever any character matches with both the array then we need to increment the value by 1 and carry on with same comparison for all rows and columns.
Same comparison will be done using recursion and by storing the value to achieve dynamic programming.  

public class LCS {

 public static void main(String[] args) {

  String str1 = "ABAZDC";
  String str2 = "BACBAD";

  LCS obj = new LCS();
  String out = obj.getLCS(str1, str2);

  System.out.println("LCS Length : " + out.length());
  System.out.println("LCS String : " + out);
 }

 public String getLCS(String str1, String str2) {

  /* Array will be updated with the character change order */
  int arr[][] = new int[str1.length()][str2.length()];
  
  /* Calling actual LCS recursive method */
  getLCS(str1, str1.length() - 1, str2, str2.length() - 1, arr);

  return constructLCSString(arr, str1, str2);
 }
 
 /*
  * Constructing the LCS string the generated array arr[]
  */
 public String constructLCSString(int[][] arr, String str1, String str2) {
  
  String lcsString = "";
  
  /* Iterating through arr[] to get the actual LCS string 
   * iterating from bottom to up.
   */
  for (int i = arr.length - 1, j = arr[0].length - 1; (i >= 0 && j >= 0);) {

   if (i == 0) {
    lcsString = str1.charAt(i) + lcsString;
    break;
   } else if (j == 0) {
    lcsString = str2.charAt(j) + lcsString;
    break;
   }

   if (arr[i][j] != arr[i - 1][j] && arr[i][j] != arr[i][j - 1]) {
    lcsString = str1.charAt(i) + lcsString;
    i--;j--;
   } else if (arr[i][j] == arr[i - 1][j]) {
    i--;
   } else if (arr[i][j] == arr[i][j - 1]) {
    j--;
   }
  }
  return lcsString;
 }
 
 
 public int getLCS(String str1, int n, String str2, int m, int arr[][]) {
  if (n == -1 || m == -1)
   return 0;
  
  /*
   * Checking in array for same n, m index and if present returning 
   * the value from array and its Dynamic programming
   */
  if (arr[n][m] != 0)
   return arr[n][m];

  int output = 0;
  if (str1.charAt(n) == str2.charAt(m)) {
   output = 1 + getLCS(str1, n - 1, str2, m - 1, arr);
  } else {
   int tmp1 = getLCS(str1, n - 1, str2, m, arr);
   int tmp2 = getLCS(str1, n, str2, m - 1, arr);
   output = tmp1 > tmp2 ? tmp1 : tmp2;
  }
  /* Memorize the output on array to use for similar recursive call */
  arr[n][m] = output;
  return output;
 }
}

OUTPUT:

LCS Length : 4
LCS String : ABAD

Dynamic Programming - Find nth Fibonacci number

Dynamic Programming - Find nth Fibonacci number

recursion  

Dynamic Programming (DP) is an algorithmic that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again for another subproblems. Just make use of the previously computed result by storing and by this complexity will be reduced. Usually we used to write a recursive call for getting list of Fibonacci series or to get the nth element in Fibonacci series. Here we will see simple recursive method for getting nth Fibonacci number with and without dynamic programming and latter will compare the benefits of using DP.

Find nth Fibonacci number using recursive:

public class Fibonacci {
 
 static int i = 0;
 
 public static void main(String[] args) {
  int n = 10;
  int val = fibo(n);
  System.out.println("No. of recursive calls : "+i);
  System.out.println(n +"th Fibonacci number : "+val);
  
 }
 
 public static int fibo(int n) {
  System.out.println("CALL ::: "+ (++i) + " - n: "+n);
  if(n<=2) {
   return 1;
  }
  else {
   int f = fibo(n-1) + fibo(n-2);
   return f;
  }
 }
}

OUTPUT:

CALL ::: 1 - n: 10
CALL ::: 2 - n: 9
CALL ::: 3 - n: 8
CALL ::: 4 - n: 7
CALL ::: 5 - n: 6
CALL ::: 6 - n: 5
CALL ::: 7 - n: 4
CALL ::: 8 - n: 3
CALL ::: 9 - n: 2
CALL ::: 10 - n: 1
CALL ::: 11 - n: 2
CALL ::: 12 - n: 3
CALL ::: 13 - n: 2
CALL ::: 14 - n: 1
CALL ::: 15 - n: 4
CALL ::: 16 - n: 3
CALL ::: 17 - n: 2
CALL ::: 18 - n: 1
CALL ::: 19 - n: 2
CALL ::: 20 - n: 5
CALL ::: 21 - n: 4
CALL ::: 22 - n: 3
CALL ::: 23 - n: 2
CALL ::: 24 - n: 1
CALL ::: 25 - n: 2
CALL ::: 26 - n: 3
CALL ::: 27 - n: 2
CALL ::: 28 - n: 1
CALL ::: 29 - n: 6
CALL ::: 30 - n: 5
CALL ::: 31 - n: 4
CALL ::: 32 - n: 3
CALL ::: 33 - n: 2
CALL ::: 34 - n: 1
CALL ::: 35 - n: 2
CALL ::: 36 - n: 3
CALL ::: 37 - n: 2
CALL ::: 38 - n: 1
CALL ::: 39 - n: 4
CALL ::: 40 - n: 3
CALL ::: 41 - n: 2
CALL ::: 42 - n: 1
CALL ::: 43 - n: 2
CALL ::: 44 - n: 7
CALL ::: 45 - n: 6
CALL ::: 46 - n: 5
CALL ::: 47 - n: 4
CALL ::: 48 - n: 3
CALL ::: 49 - n: 2
CALL ::: 50 - n: 1
CALL ::: 51 - n: 2
CALL ::: 52 - n: 3
CALL ::: 53 - n: 2
CALL ::: 54 - n: 1
CALL ::: 55 - n: 4
CALL ::: 56 - n: 3
CALL ::: 57 - n: 2
CALL ::: 58 - n: 1
CALL ::: 59 - n: 2
CALL ::: 60 - n: 5
CALL ::: 61 - n: 4
CALL ::: 62 - n: 3
CALL ::: 63 - n: 2
CALL ::: 64 - n: 1
CALL ::: 65 - n: 2
CALL ::: 66 - n: 3
CALL ::: 67 - n: 2
CALL ::: 68 - n: 1
CALL ::: 69 - n: 8
CALL ::: 70 - n: 7
CALL ::: 71 - n: 6
CALL ::: 72 - n: 5
CALL ::: 73 - n: 4
CALL ::: 74 - n: 3
CALL ::: 75 - n: 2
CALL ::: 76 - n: 1
CALL ::: 77 - n: 2
CALL ::: 78 - n: 3
CALL ::: 79 - n: 2
CALL ::: 80 - n: 1
CALL ::: 81 - n: 4
CALL ::: 82 - n: 3
CALL ::: 83 - n: 2
CALL ::: 84 - n: 1
CALL ::: 85 - n: 2
CALL ::: 86 - n: 5
CALL ::: 87 - n: 4
CALL ::: 88 - n: 3
CALL ::: 89 - n: 2
CALL ::: 90 - n: 1
CALL ::: 91 - n: 2
CALL ::: 92 - n: 3
CALL ::: 93 - n: 2
CALL ::: 94 - n: 1
CALL ::: 95 - n: 6
CALL ::: 96 - n: 5
CALL ::: 97 - n: 4
CALL ::: 98 - n: 3
CALL ::: 99 - n: 2
CALL ::: 100 - n: 1
CALL ::: 101 - n: 2
CALL ::: 102 - n: 3
CALL ::: 103 - n: 2
CALL ::: 104 - n: 1
CALL ::: 105 - n: 4
CALL ::: 106 - n: 3
CALL ::: 107 - n: 2
CALL ::: 108 - n: 1
CALL ::: 109 - n: 2
No. of recursive calls : 109
10th Fibonacci number : 55

If we seen above output we can get to know that just for 10th Fibonacci number total 109 recursive calls made. Also in many cases like Fibo(4), Fibo(5), Fino(3) etc., are multiple times computed for same value. So here we need to use the power of Dynamic Programming to store the computed value and need to reuse the result if same value occurs again. By this we can avoid lot of iterations/recursive call's.

Lets see converting above program to Dynamic Programming by storing the computed value and reusing it again when its need. By this lets find out how many recursive calls made for getting 10th Fibonacci number.

Find nth Fibonacci number using Dynamic Programming:

import java.util.HashMap;

public class Fibonacci {
 
 static int i = 0;
 static HashMap<Integer, Integer> map = new HashMap<>();
 
 public static void main(String[] args) {
  int n = 10;
  int val = fibo(n);
  System.out.println("No. of recursive calls : "+i);
  System.out.println(n +"th Fibonacci number : "+val);
  
 }
 
 public static int fibo(int n) {
  
  if(map.containsKey(n)) 
   return map.get(n);
  
  System.out.println("CALL ::: "+ (++i) + " - n: "+n);
  if(n<=2) {
   map.put(n, 1);
   return 1;
  }
  else {
   int f = fibo(n-1) + fibo(n-2);
   map.put(n, f);
   return f;
  }
 }
}

OUTPUT:

CALL ::: 1 - n: 10
CALL ::: 2 - n: 9
CALL ::: 3 - n: 8
CALL ::: 4 - n: 7
CALL ::: 5 - n: 6
CALL ::: 6 - n: 5
CALL ::: 7 - n: 4
CALL ::: 8 - n: 3
CALL ::: 9 - n: 2
CALL ::: 10 - n: 1
No. of recursive calls : 10
10th Fibonacci number : 55

Now we can compare the no. of recursive calls made my 1st program and 2nd program exactly to get the same output of 10th Fibonacci number. If we see 1st program taken 109 recursive calls and 2nd dynamic program taken only 10 recursive calls for same problem and output.