Top-Down Approach for Palindrome Partitioning Problem

Top-down approach; pseudocode with java codes and references
Pseudocode and description of the problem using top-down approach ,recursion and memoization.
Given input as String strin;
// i is the beginning index passed as i=0 while j marks the end index j=n-1;
Using recurrence, search for the partions and then store them in an array while making Boolean array
true; Below is an optimal substructure of the program
//Base cases
If the length of string ==1
BestPal(strin,i,j)=1;
If the String is a palindrome then
Bestpal(strin,i,j)==1;
If both of them are false,then
Bespal(strin,i,j) is computed through recurrence implementing the following formula
Bestpal(strin,i,j)=Minimum{Bestpal(strin,i,k) + k + 1 + Bestpal(strin,i,k +1,j)}
Where the k changes ranging from (i) to j-1;
Note if a more optimized solution is needed ,of which your assignments requires then the first
bottom up approach is advised due to its complexity of O(n2) unlike this which is O(n3);
Below is a java program to implement the pseudocode using Dynamic Programming solution storing the
correct answers to subproblems in two arrays namely pal[][] and count[][], and keeps reusing the
values stored:
import java.io.*;
import java.util.*;
public class findpalindromes
{
//java program to find the minimum cuts in palindromic partioning using top-down
approach and memoization technique
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
String s=in.next();
//String s=“madamanna”;
System.out.println("The value of Best-palindrome of string s is" + bestpal(s));
}
//this method Returns the integer representing number
// of partitioning the given string to ensure each
// part is a palindrome
static int bestpal(String strin)
{
//let length to be the length of the given string
int length=strin.length();
/* We need to create two arrays to store , compute and check if values therein are
computed and if not then we create one
count[i][j]=this represents the min no of cuts required for palindrome partitioning