Dynamic Programming

here we can see some of the Dynamic Programming concepts and the sample program to implement those concepts

Normally Dynamic Programming works on the concepts of recursion and

DIVIDE & CONQUER

rule

1) java program to find the maximum number of paths to reach from top left to bottom right of a matrix

import java.util.*;
class Hello { 
    
    static int numberOfPaths(int m, int n) 
    { 
    
        if (m == 1 || n == 1) 
            return 1; 
  

        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1); 
       
    } 
  
    public static void main(String args[]) 
    { 
        Scanner sc=new Scanner(System.in);
        int R=sc.nextInt();
        int C=sc.nextInt();
        System.out.println(numberOfPaths(R, C)); 
    } 
} 


Sample input:
2 2
Sample output:
2
There are two paths
(0, 0) -> (0, 1) -> (1, 1)
(0, 0) -> (1, 0) -> (1, 1)

Sample input:  
2 3
Sample Output : 
3
There are three paths
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2)
(0, 0) -> (0, 1) -> (1, 1) -> (1, 2)
(0, 0) -> (1, 0) -> (1, 1) -> (1, 2)
Java program to find the maximum cost to reach the end point

import java.util.*;
public class Hello { 
  
    static int min(int x, int y, int z) 
    { 
        if (x < y) 
            return (x < z) ? x : z; 
        else
            return (y < z) ? y : z; 
    }  
    static int minCost(int cost[][], int m, int n) 
    { 
        if (n < 0 || m < 0) 
            return Integer.MAX_VALUE; 
        else if (m == 0 && n == 0) 
            return cost[m][n]; 
        else
            return cost[m][n] +  
                min( minCost(cost, m-1, n-1), 
                     minCost(cost, m-1, n),  
                     minCost(cost, m, n-1) ); 
    } 
   
    public static void main(String args[])  
    {       
        Scanner sc=new Scanner(System.in);
        int R=sc.nextInt();
        int C=sc.nextInt();
        int[][] cost=new int[R][C];
        for(int i=0;i<R;i++)
        {
            for(int j=0;j<C;j++)
            {
                cost[i][j]=sc.nextInt();
            }
        }
                           
        System.out.print(minCost(cost, 2, 2)); 
    } 
} 

input:
3 3
1 2 3
4 8 2
1 5 3
output:
8
Java program to find the minimum cost to reach from 0 to N in an integer

import java.util.*;
public class Hello {
    
static int minCost(int N, int P, int Q) 
{ 
    int cost = 0; 
    while (N > 0) { 
  
        if ((N & 1)>0) { 
            cost += P; 
            N--; 
        } 
        else { 
            int temp = N / 2; 
            if (temp * P > Q) 
                cost += Q; 
            else
                cost += P * temp; 
            N /= 2; 
        } 
    } 
    return cost; 
} 
public static void main(String[] args) 
{ 
    Scanner sc=new Scanner(System.in);
    int N=sc.nextInt();
    int P=sc.nextInt();
    int Q=sc.nextInt();
    System.out.println(minCost(N, P, Q)); 
} 
} 

input:
5 2 3
output:
9

explanation:
here N=5,P=2,Q=3
-to incement from 0 to 1, there is a cost of 2.
-to increment from 1 to 2, there is a cost of 2(doubline cost is 3 so we just increment 1 to 2 which attracys only a cost of 2).
-to double from 2 to 4, there is a cost of 2.
-to increment from 4 to 5, there is a cost of 2.
hence total minimum cost is 2+2+3+2=9.

input:
4 1 5
output:
4
Java program to collect the maximum points in a matrix

import java.uti.*;
class Main
{
public static int max(int a,int b)
{
    return (a>b)?a:b;
}

public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int R=sc.nextInt();
int C=sc.nextInt();
int[][] mat=new int[100][100];
int[][] ans=new int[100][100];
for(int i=0;i<R;i++)
{
    for(int j=0;j<C;j++)
    {
        mat[i][j]=sc.nextInt();
    }
}
int k=0;
for(int i=0;i<C;i++)
{
    ans[i][0]=mat[i][k];
}
int maxv=0;
for(int j=1;j<C;j++)
{
    for(int i=0;i<R;i++)
    {
        if(i==0)
        {
            ans[i][j]=max(ans[i][j-1],ans[i+1][j-1])+mat[i][j];
        }
        else if(i==R-1)
        {
            ans[i][j]=max(ans[i][j-1],ans[i-1][j-1])+mat[i][j];
        }
        else
        {
            ans[i][j]=max(ans[i][j-1],max(ans[i-1][j-1],ans[i+1][j-1]))+mat[i][j];
        }
        if(j==C-1&&(ans[i][j]>maxv))
        {
            maxv=ans[i][j];
        }
    }
}
System.out.print(maxv);
}

input:
3 3
5 3 3
2 1 4
0 9 4
output:
15

input:
4 4
1 3 1 1
2 2 4 1
5 0 2 3
0 6 1 2
output:
16

input:
10 10
80 32 29 39 0 13 88 12 89 96
48 72 47 55 49 79 7 74 65 33
48 76 89 60 81 31 47 79 48 6
17 24 78 28 79 46 31 45 74 9
92 85 85 8 68 32 56 40 80 93
58 41 35 43 86 46 32 98 33 48
100 13 5 60 27 65 98 84 85 75
11 66 22 96 86 97 64 47 54 10
44 40 93 11 21 83 82 39 7 49
59 33 80 28 55 55 37 59 99 42
output:
907

input:
4 4
1 3 1 7
2 2 4 1
5 0 2 3
0 8 1 2
output:
18
Java program to find the minimum weight in the cart (Jhony's ammusement park)

import java.util.*;
class Main
{
static int max(int a,int b)
{
    return (a>b)?a:b;
}

static int min(int a,int b)
{
    return (a<b)?a:b;
}

public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int[][] matrix=new int[N][N];
for(int row=0;row<N;row++)
{
    for(int col=0;col<N;col++)
    {
        &matrix[row][col]=sc.nextInt();
    }
}
int[][] weight=new int[N][N];

//fill the top left corner
weight[0][0]=matrix[0][0]; 

//fill the first row
for(int row=1;row<N;row++)
{
    weight[row][0]=max(matrix[row][0],weight[row-1][0]);
}

//fill the first column
for(int col=1;col<N;col++)
{
     weight[0][col]=max(matrix[0][col],weight[0][col-1]);
}  

//fill the remaining part of the matrix
for(int row=1;row<N;row++)
{
    for(int col=1;col<N;col++)
    {
        int min_weight=min(weight[row][col-1],weight[row-1][col]);
        //col-1  --> leftside ; //row-1  --> top side;
        
        weight[row][col]=max(min_weight,matrix[row][col]);
    }
}
System.out.print(weight[N-1][N-1]);
}
}
Java program to find the ugly number of the given number

import java.util.*;
class Main { 
     
    static int maxDivide(int a, int b) 
    { 
        while(a % b == 0) 
            a = a/b; 
        return a; 
    } 

    static int isUgly(int no) 
    { 
        no = maxDivide(no, 2); 
        no = maxDivide(no, 3); 
        no = maxDivide(no, 5); 
          
        return (no == 1)? 1 : 0; 
    } 

    static int getNthUglyNo(int n) 
    { 
        int i = 1; 
          
        int count = 1;  
  
        while(n > count) 
        { 
            i++; 
            if(isUgly(i) == 1) 
                count++; 
        } 
        return i; 
    } 
      
    public static void main(String args[]) 
    { 
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int no = getNthUglyNo(N); 
        System.out.println("150th ugly "+"no. is "+ no); 
    } 
} 

Input  : N = 7
Output : 8

Input  : N = 10
Output : 12

Input  : N = 15
Output : 24

Input  : N = 150
Output : 5832
Java program to find the Nth term in fibonacci series

import java.util.*;
class Main 
{ 
    static int fib(int n) 
    { 
    if (n <= 1) 
       return n; 
    return fib(n-1) + fib(n-2); 
    } 
       
    public static void main (String args[]) 
    { 
     Scanner sc=new Scanner(System.in);
    int n = sc.nextInt(); 
    System.out.println(fib(n)); 
    } 
} 

Input  : n = 2
Output : 1

Input  : n = 9
Output : 34
Java program to find the Nth catalan number using binomial coefficient method

import java.util.*;
class Main { 
   
    static long binomialCoeff(int n, int k) { 
        long res = 1; 
  
        if (k > n - k) { 
            k = n - k; 
        } 

        for (int i = 0; i < k; ++i) { 
            res *= (n - i); 
            res /= (i + 1); 
        } 
  
        return res; 
    } 
   
    static long catalan(int n) 
    { 
        long c = binomialCoeff(2 * n, n);  
        return c / (n + 1); 
    } 
  
    public static void main(String[] args) 
    { 
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        for (int i = 0; i < N; i++) { 
            System.out.print(catalan(i) + " "); 
        } 
  
    } 
}

input:
10 

output:
1 1 2 5 14 42 132 429 1430 4862

explanation:
We can also use below formula to find nth catalan number in O(n) time.
Cn = (2n)! / ((n + 1)!n!) 
Java program to count number of ways to partition a set into K subsets

import java.util.*; 
  
class GFG 
{ 
    public static int countP(int n, int k) 
    { 

       if (n == 0 || k == 0 || k > n) 
          return 0; 
       if (k == 1 || k == n) 
          return 1; 
]
       return (k * countP(n - 1, k)  
              + countP(n - 1, k - 1)); 
    } 
  
    public static void main(String args[]) 
    { 
       Scanner sc=new Scanner(System.in)
       int N=sc.nextInt();
       int K=sc.nextInt();
       System.out.println(countP(N, K)); 
  
    } 
} 

Input: n = 3, k = 2
Output: 3
Explanation: Let the set be {1, 2, 3}, we can partition
             it into 2 subsets in following ways
             {{1,2}, {3}},  {{1}, {2,3}},  {{1,3}, {2}}  

Input: n = 3, k = 1
Output: 1
Explanation: There is only one way {{1, 2, 3}}
Java program to find the size of submatrix which contains all 1's

import java.util.*;
public class Hello {

    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[][] mat=new int[n][n];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                mat[i][j]=sc.nextInt();
            }
        }
        int R=n,C=n;
        int[][] dp=new int[R][C];
        for(int i=0;i<R;i++)
        {
            dp[i][0]=mat[i][0];
        }
        for(int j=0;j<C;j++)
        {
            dp[0][j]=mat[0][j];
        }
        for(int i=1;i<R;i++)
        {
            for(int j=1;j<C;j++)
            {
                if(mat[i][j]==1)
                {
                    dp[i][j]=Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]))+1;
                }
                else{
                    dp[i][j]=0;
                }
            }
        }
        int maxsize=0;
        for(int i=0;i<R;i++)
        {
            for(int j=0;j<C;j++)
            {
                if(maxsize<dp[i][j])
                {
                    maxsize=dp[i][j];
                }
            }
        }
        System.out.print(maxsize*maxsize);
  }
}

sample input 1:
4
1 1 0 1
1 1 0 0
0 1 1 1
0 1 0 1

sample output 1:
4

sample input 2:
6
1 0 1 1 1 0
1 0 1 1 1 1
0 0 1 1 1 0 
1 0 1 0 1 1
0 0 1 0 1 0
1 0 1 1 1 0

sample output 2:
9
Find the Length of Longest Anagram Sequence in two strings

import java.util.*;
public class Main
{
    public static int findCount(String str1,String str2)
    {
        int l1=str1.length();
        int l2=str2.length();
        int[] freq1=new int[26];
        int[] freq2=new int[26];
        Arrays.fill(freq1,0);
        Arrays.fill(freq2,0);
        for(int index1=0;index1<l1;index1++)
        {
            freq1[str1.charAt(index1)-'a']++;
        }
        for(int index2=0;index2<l2;index2++)
        {
            freq2[str2.charAt(index2)-'a']++;
        }
        int count=0;
        for(int index=0;index<26;index++)
        {
            count+=Math.min(freq1[index],freq2[index]);
        }
        return count;
    }
    public static void main (String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        String str1=sc.next();
        String str2=sc.next();
        System.out.print(findCount(str1,str2));
    }
}
Input 1:
abdacp
ckamb

Output 1:
3

Input 2:
abbcfke
fbaafbly

Output 2:
4
String distance - 2 edits

import java.util.*;
public class Main
{
    static int editdistance2Edits(String s1,String s2,int m,int n)
    {
        int[][] edit=new int[m+1][n+1];
        for(int index1=0;index1<=m;index1++)
        {
            for(int index2=0;index2<=n;index2++)
            {
                if(index1==0||index2==0)
                edit[index1][index2]=0;
                else if(s1.charAt(index1-1)==s2.charAt(index2-1))
                edit[index1][index2]=edit[index1-1][index2-1]+1;
                else
                edit[index1][index2]=Math.max(edit[index1-1][index2],edit[index1][index2-1]);
            }
        }
        return (m-edit[m][n])+(n-edit[m][n]);
    }
    public static void main (String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        String str1=sc.next();
        String str2=sc.next();
        int l1=str1.length();
        int l2=str2.length();
        System.out.print(editdistance2Edits(str1,str2,l1,l2));
    }
}

input 1:
cat
cut

output 1:
2

input 2:
sunday 
saturday

output 2:
4
String edit-distance

import java.util.*;
pubic class Main
{
    static int  editDistance(String s1,String s2,int m,int n)
    {
        int edit[][]=new int[m+1][n+1];
        for(int i=0;i<=m;i++)
        {
            for(int j=0;j<=n;j++)
            {
                if(i==0)
                edit[i][j]=j;
                else if(j==0)
                edit[i][j]=i;
                else if(s1.charAt(i-1)==s2.charAt(j-1))
                edit[i][j]=edit[i-1][j-1];
                else
                edit[i][j]=1+Math.min(Math.min(edit[i-1][j],edit[i][j-1]),edit[i-1][j-1]);
            }
        }
        return edit[m][n];
    }
    
 public static void main (String[] args) 
 {
     Scanner sc=new Scanner(System.in);
     String s1=sc.next();
     String s2=sc.next();
     int m=s1.length();
     int n=s2.length();
     System.out.print(editDistance(s1,s2,m,n));
 }
}
input 1:
cat
cut

output 1:
1

input 2:
sunday 
saturday

output 2:
3
Longest Palindromic Substring Length

import java.util.*;
public class Main
{
    static int longestPalindrome(String str)
    {
        int maxlen=1,start=0,low,high;
        int len=str.length();
        for(int i=1;i<len;++i)
        {
            low=i-1;
            high=i;
            while(low>0&&high<len&&str.charAt(low)==str.charAt(high))
            {
                if(high-low+1>maxlen)
                {
                    start =low;
                    maxlen=high-low+1;
                }
                --low;
                ++high;
            }
            low=i-1;
            high=i+1;
            while(low>=0&&high<len&&str.charAt(low)==str.charAt(high))
            {
                if(high-low+1>maxlen)
                {
                    start=low;
                    maxlen=high-low+1;
                }
                --low;
                ++high;
            }
        }
        return maxlen;
    }
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        String str=sc.nextLine();
        int len=str.length();
        System.out.print("Length of longest palindromic substring is "+longestPalindrome(str));
        
    }
}
input 1:
bananas

output 1:
5 
Longest Common Subsequence Length

import java.util.*;
public class Main
{
    public static int lcs(char[] x,char[] y,int a,int b)
    {
        if(a==0||b==0)
        {
            return 0;
        }
        else if(x[a-1]==y[b-1])
        {
            return 1+lcs(x,y,a-1,b-1);
        }
        else
        {
            return Math.max(lcs(x,y,a-1,b),lcs(x,y,a,b-1));
        }
    }
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        String str1=sc.next();
        String str2=sc.next();
        char[] x=str1.toCharArray();
        char[] y=str2.toCharArray();
        System.out.print("LCS length is "+lcs(x,y,str1.length(),str2.length()));
    }
}

Input 1:
AGGTAB
GXTXAYB

Output 1:
LCS length is 4
Minimum deletions to form a palindrome

import java.util.*;
public class Main
{
    static int findMindeletion(char str[],int x,int y)
    {
        if(x>y)
        {
            return x;
        }
        else if(x==y)
        {
            return 0;
        }
        else if(x==y-1)
        {
            return (str[x]==str[y])?0:1;
        }
        else
        {
            return (str[x]==str[y])?findMindeletion(str,x+1,y-1):(Integer.min(findMindeletion(str,x,y-1),findMindeletion(str,x+1,y))+1);
        }
    }
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the String:");
        String str=sc.nextLine();
        int n=str.length();
        System.out.print("The minimum number of deletions required are "+findMindeletion(str.toCharArray(),0,n-1));
    }
}

Input1:
Enter the String:
madm

Output1:
The minimum number of deletions required are 1

Input2:
Enter the String:
welcome

Output2:
The minimum number of deletions required  are 4
Vowel count in Sliding Window:(with o(n) time complexity)

import java.util.*;
public class Main 
{
    static int isVowel(char c)
    {
        if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='A'||c=='E'||c=='I'||c=='O'||c=='U')
        return 1;
        else
        return 0;
    }
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        String str=sc.next();
        int l=str.length();
        int count=0;
        for(int index=0;index<N;index++)
        {
            if(isVowel(str.charAt(index))==1)
            count++;
        }
        System.out.print(count+" ");
        for(int index=N;index<l;index++)
        {
            count=count-(isVowel(str.charAt(index-N)));
            count=count+(isVowel(str.charAt(index)));
            System.out.print(count+" ");
        }
  }
}

input 1:
4                                                                                                                             
environment  
output 1:
2 1 2 2 1 2 1 1

input 2:
2
SKILLRACK
output 2:
0 1 1 0 0 1 1 0
Sliding Window array sum: (with O(n) time complexity)

import java.util.*;
public class Main 
{
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();              
        int[] arr=new int[N];
        for(int index=0;index<N;index++)
        {
            arr[index]=sc.nextInt();
        }
        int K=sc.nextInt();
        int sum=0;
        for(int index=0;index<K;index++)
        {
            sum=sum+arr[index];
        }
        System.out.print(sum+" ");
        for(int index=K;index<N;index++)
        {
            sum=sum-arr[index-K];
            sum=sum+arr[index];
            System.out.print(sum+" ");
        }
  }
}

input 1:
7
5 80 90 5 30 42 4                                                                                                             
3  
output 1:
175 175 125 77 76 
Robot movement - Maximum possible steps:


import java.util.*;
public class Main 
{
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int N=sc.nextInt();
  int ways=sc.nextInt();
  long[] totalWays=new long[N+1];
  int[] Ways=new int[N+1];
  for(int index=0;index<ways;index++)
  {
      Ways[index]=sc.nextInt();
  }
  totalWays[0]=1;
  for(int step=1;step<=N;step++)
  {
      for(int way=0;way<ways;way++)
      {
          if(step>=Ways[way])
          {
              totalWays[step]+=totalWays[step-Ways[way]];
          }
      }
  }
  System.out.print(totalWays[N]);
 }
}

input 1:
5 2                                                                                                                             
2 3  

output 1:
2

input 2:
24 4                                                                                                                            
2 3 6 5 

output 2:
3953
Robot movement - skip Damaged steps:

import java.util.*;
public class Main 
{
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int N=sc.nextInt();
  int ways=sc.nextInt();
  int damage=sc.nextInt();
  long[] totalWays=new long[N+1];
  int[] Ways=new int[N+1];
  List<Integer> Damage=new ArrayList<>();
  for(int index=0;index<ways;index++)
  {
      Ways[index]=sc.nextInt();
  }
  for(int index=1;index<=damage;index++)
  {
      Damage.add(sc.nextInt());
  }
  totalWays[0]=1;
  for(int step=1;step<=N;step++)
  {
      if(Damage.contains(step))
      {
          totalWays[step]=0;
          continue;
      }
      for(int way=0;way<ways;way++)
      {
          if(step>=Ways[way])
          {
              totalWays[step]+=totalWays[step-Ways[way]];
          }
      }
  }
  System.out.print(totalWays[N]);
 }
}

input 1:
5 2 1                                                                                                                           
2 3                                                                                                                             
2  

output 1:
1

input 2:
18 3 2                                                                                                                          
2 3 5                                                                                                                           
4 13  

output 2:
81
Robot Movement - skip slippery step:

import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
   Scanner sc=new Scanner(System.in);
  int N=sc.nextInt();
  int ways=sc.nextInt();
  int slip=sc.nextInt();
  long[] totalWays=new long[N+1];
  totalWays[0]=1;
  int[] Ways=new int[ways+1];
  List<Integer> Slippery=new ArrayList<>();
  for(int way=0;way<ways;way++)
  {
      Ways[way]=sc.nextInt();
  }
  for(int index=1;index<=slip;index++)
  {
      Slippery.add(sc.nextInt());
  }
  for(int step=1;step<=N;step++)
  {
      for(int way=0;way<ways;way++)
      {
          if(step>=Ways[way])
          {
              totalWays[step]+=totalWays[step-Ways[way]];
          }
      }
      if(Slippery.contains(step))
      {
          int lastNonSlippery=step-1;
          while(Slippery.contains(lastNonSlippery)&&lastNonSlippery>0)
          {
              lastNonSlippery--;
          }
          if(lastNonSlippery>0)
          {
              totalWays[lastNonSlippery]+=totalWays[step];
          }
          totalWays[step]=0;
      }
  }
  System.out.print(totalWays[N]);
 }
}

input 1:
5 2 1                                                                                                                           
2 3                                                                                                                             
2  

output 1:
2

input 1:
18 4 3                                                                                                                          
3 2 4 6                                                                                                                         
2 6 12  

output 1:
800
Maximum sum -  non adjacent elements:

import java.util.*;
public class Main
{
    static int findMaxSum(int[] arr,int n)
    {
        int num1=arr[0],num2=0,ans=0;
        for(int index=1;index<n;index++)
        {
            if(num1>num2)
            ans=num1;
            else
            ans=num2;
            num1=num2+arr[index];
            num2=ans;
        }
        return ((num1>num2)?num1:num2);
    }
    public static void main(String[] args)
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int[] arr=new int[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextInt();
  }
  System.out.print(findMaxSum(arr,n));
 }
}

input 1:
10
35 47 27 67 56 1 19 28 8 40

output 1:
186

input 2:
5
2 3 4 4 1

output 2:
7
Maximum sum of subarray :

import java.util.*;
public class Main
{
    static int maxSubArray(int[] arr)
    {
        int maxSum=arr[0],sum=arr[0];
        for(int index=1;index<arr.length;index++)
        {
            sum=Math.max(arr[index],sum+arr[index]);
            maxSum=Math.max(maxSum,sum);
        }
        return maxSum;
    }
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int[] arr=new int[n];
  for(int index=0;index<n;index++)
  {
      arr[index]=sc.nextInt();
  }
  System.out.print(maxSubArray(arr));
 }
}

input 1:
3
-5 -4 -6
Output 1:
-4

input 2:
5
5 4 -3 -5 6
output 2:
9
Longest Common Substring  Length:

import java.util.*;
public class Main 
{
    static int findLCS(String str1,String str2)
    {
        int l1=str1.length();
        int l2=str2.length();
        int[][] dp=new int[l1+1][l2+1];
        int max=0;
        for(int index1=1;index1<=l1;index1++)
        {
            for(int index2=1;index2<=l2;index2++)
            {
                if(str1.charAt(index1-1)==str2.charAt(index2-1))
                {
                    dp[index1][index2]=dp[index1-1][index2-1]+1;
                    if(dp[index1][index2]>max)
                    {
                        max=dp[index1][index2];
                    }
                }
            }
        }
        return max;
    }
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  String str1=sc.next();
  String str2=sc.next();
  System.out.print(findLCS(str1,str2));
 }
}

input 1:
nose
raise

output 1:
2

input 2:
fever
lever

output 2:
4
Length of longest substring with equal alphabets and digits:

import java.util.*;
public class Main 
{
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  String str=sc.next();
  Map<Integer,Integer> hm=new HashMap<>();
  int max=0,l=str.length(),count=0,position=0;
  hm.put(count,position);
  for(int index1=0;index1<l;index1++)
  {
      position++;
      if(Character.isLetter(str.charAt(index1)))
      {
         count++;
      }
      else if(Character.isDigit(str.charAt(index1)))
      {
          count--;
      }
      if(hm.containsKey(count))
      {
          int currLen=position-hm.get(count);
          if(currLen>max)
          max=currLen;
      }
      else
      hm.put(count,position);
  }
  System.out.print(max);
 }
}

input 1:
abz23aacc1567

output 1:
12

input 2:
ab547b63

output 2:
6
Total Possible Dribbling paths of a basketball player:

import java.util.*;
import java.math.*;

public class Main 
{
    static void setRowValue(BigInteger[][] totalPaths,int C)
    {
        for(int col=0;col<C;col++)
        {
            totalPaths[0][col]=BigInteger.valueOf(1);
        }
    }
    static void setColValue(BigInteger[][] totalPaths,int R)
    {
        for(int row=0;row<R;row++)
        {
            totalPaths[row][0]=BigInteger.valueOf(1);
        }
    }
    static BigInteger findTotalPaths(int R,int C)
    {
        BigInteger[][] totalPaths=new BigInteger[R][C];
        setRowValue(totalPaths,C);
        setColValue(totalPaths,R);
        for(int row=1;row<R;row++)
        {
            for(int col=1;col<C;col++)
            {
                totalPaths[row][col]=totalPaths[row-1][col].add(totalPaths[row][col-1]);
            }
        }
        return totalPaths[R-1][C-1];
    }
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int R=sc.nextInt();
  int C=sc.nextInt();
  System.out.print(findTotalPaths(R,C));
 }
}

input 1:
2 3
output 1:
3

input 2:
3 3
output 2:
6

input 3:
25 21
output 3:
1761039350070

input 4:
100 91
output 4:
36744876179076249096579888358334560698439034159836506900
Collect Maximum points in a matrix:

import java.util.*;
public class Main 
{
    static int findMaxPoints(int[][] mat,int R,int C)
    {
        int[][] points=new int[R][C];
        points[0][0]=mat[0][0];
        for(int row=1;row<R;row++)
        {
            points[row][0]=points[row-1][0]+mat[row][0];
        }
        for(int col=1;col<C;col++)
        {
            points[0][col]=points[0][col-1]+mat[0][col];
        }
        for(int row=1;row<R;row++)
        {
            for(int col=1;col<C;col++)
            {
                points[row][col]=mat[row][col]+Math.max(points[row][col-1],points[row-1][col]);
                
            }
        }
        return points[R-1][C-1];
    }
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int R=sc.nextInt();
  int C=sc.nextInt();
  int[][] mat=new int[R][C];
  for(int row=0;row<R;row++)
  {
      for(int col=0;col<C;col++)
      {
          mat[row][col]=sc.nextInt();
      }
  }
  System.out.print(findMaxPoints(mat,R,C));
 }
}

input 1:
4 5
4 2 9 6 1
7 9 6 5 4
5 7 3 8 8
7 4 9 9 4

output 1:
53
Collect Maximum points from starting point till end:

import java.util.*;
public class Main
{
    static int findMaxPoints(int[][] mat,int R,int C,int startRow,int startCol)
    {
        int[][] points=new int[R][C];
        points[startRow][startCol]=mat[startRow][startCol];
        for(int row=startRow+1;row<R;row++)
        {
            points[row][startCol]=points[row-1][startCol]+mat[row][startCol];
        }
        for(int col=startCol+1;col<C;col++)
        {
            points[startRow][col]=points[startRow][col-1]+mat[startRow][col];
        }
        for(int row=startRow+1;row<R;row++)
        {
            for(int col=startCol+1;col<C;col++)
            {
                points[row][col]=mat[row][col]+Math.max(points[row][col-1],points[row-1][col]);
            }
        }
        return points[R-1][C-1];
        
    }
    public static void main(String[] args) 
    {
   Scanner sc=new Scanner(System.in);
  int R=sc.nextInt();
  int C=sc.nextInt();
  int[][] mat=new int[R][C];
  for(int row=0;row<R;row++)
  {
      for(int col=0;col<C;col++)
      {
          mat[row][col]=sc.nextInt();
      }
  }
  int startRow=sc.nextInt();
  int startCol=sc.nextInt();
  System.out.print(findMaxPoints(mat,R,C,startRow,startCol));
 }
}

input 1:
4 5
4 2 9 6 1
7 9 6 5 4
5 7 3 8 8
7 4 9 9 4
0 1

output 1:
44