dynamic programming important question
1.longest common subsequence
import java.io.*;
class longest
{
public static int lcs(char[] x,char[] y,int m,int n)
{
int[][] a=new int[m+1][n+1];
for(int i=0;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
if(i==0 || j==0)
{
a[i][j]=0;
}
else if(x[i-1]==y[j-1])
a[i][j]=a[i-1][j-1] +1;
else
a[i][j]=Math.max(a[i-1][j],a[i][j-1]);
}
}
return a[m][n];
}
public static void main(String[] args)
{
String s1="AGGTAB";
String s2="GXTXAYB";
char[] x=s1.toCharArray();
char[] y=s2.toCharArray();
int m=x.length;
int n=y.length;
System.out.print(lcs(x,y,m,n));
}
}
Output:
4
3.Edit distance
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
class Solution
{
public int minDistance(String s1, String s2)
{
int[][] a=new int[s1.length() + 1][s2.length() +1];
for(int i=0;i<=s1.length();i++)
{
for(int j=0;j<=s2.length();j++)
{
if(i==0 && j==0)
{
a[i][j]=0;
}
else if(i==0)
{
a[i][j]=j;
}
else if(j==0)
{
a[i][j]=i;
}
else if(s1.charAt(i-1)==s2.charAt(j-1))
{
a[i][j]=a[i-1][j-1];
}
else
{
a[i][j]=1+Math.min(Math.min(a[i-1][j-1],a[i-1][j]),a[i][j-1]);
}
}
}
return a[s1.length()][s2.length()];
}
}
I
2.longest increasing subsequence
class Solution
{
public int lengthOfLIS(int[] nums)
{
int[] lis=new int[nums.length];
for(int i=0;i<nums.length;i++)
{
lis[i]=1;
}
for(int i=1;i<lis.length;i++)
{
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j] && lis[i]<lis[j]+1)
{
lis[i]=lis[j]+1;
}
}
}
int max=0;
for(int i=0;i<lis.length;i++)
{
if(lis[i]>max)
{
max=lis[i];
}
}
return max;
}
}
Note: Arrays.sort(arr, Collections.reverseOrder());
12.partition sum problem //its same problem like below first check solution of below
Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True //There is a subset (4, 5) with sum 9.
public class SubsetSum
{
public boolean subsetSum(int input[], int total)
{
boolean T[][] = new boolean[input.length + 1][total + 1];
for (int i = 0; i <= input.length; i++)
{
T[i][0] = true;
}
for (int i = 1; i <= input.length; i++)
{
for (int j = 1; j <= total; j++)
{
if (j - input[i - 1] >= 0)
{
T[i][j] = T[i - 1][j] || T[i - 1][j - input[i - 1]];
}
else
{
T[i][j] = T[i-1][j];
}
}
}
return T[input.length][total];
}
public boolean partition(int arr[])
{
int sum = 0;
for (int i = 0; i < arr.length; i++)
{
sum += arr[i];
}
if (sum % 2 != 0)
{
return false;
}
sum = sum / 2;
boolean[][] T = new boolean[arr.length + 1][sum + 1];
for (int i = 0; i <= arr.length; i++)
{
T[i][0] = true;
}
for (int i = 1; i <= arr.length; i++)
{
for (int j = 1; j <= sum; j++)
{
if (j - arr[i - 1] >= 0)
{
T[i][j] = T[i - 1][j - arr[i - 1]] || T[i - 1][j];
}
else
{
T[i][j] = T[i-1][j];
}
}
}
return T[arr.length][sum];
}
public static void main(String args[])
{
SubsetSum ss = new SubsetSum();
int arr[] = {1, 3, 5, 5, 2, 1, 1, 6};
System.out.println(ss.partition(arr));
int arr1[] = {2, 3, 7, 8};
System.out.print(ss.subsetSum(arr1, 11));
}
}
Partition a set into two subsets such that the difference of subset sums is minimum
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static void get(int[] a1,int sum)
{
boolean[][] a=new boolean[a1.length +1 ][sum + 1];
for(int i=0;i<a1.length;i++)
{
a[i][0]=true;
}
for(int i=1;i<=a1.length;i++)
{
for(int j=1;j<=sum;j++)
{
if(j-a1[i-1]>=0)
{
a[i][j]=a[i-1][j-a1[i-1]] || a[i-1][j];
}
else
{
a[i][j]=a[i-1][j];
}
}
}
int diff=Integer.MAX_VALUE;
for(int j=sum/2;j>=0;j--)
{
if(a[a1.length][j]==true)
{
diff=sum-2*j;
break;
}
}
System.out.println(diff);
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int j=0;j<n;j++)
{
int n1=sc.nextInt();
int[] a=new int[n1];
int sum=0;
for(int i=0;i<n1;i++)
{
a[i]=sc.nextInt();
sum=sum+a[i];
}
get(a,sum);//passing sum not sum/2
}
}
}
Example:
Input:
2
4
1 6 5 11
4
36 7 46 40
Output :
1
23
Maximum difference between two subsets of m elements
The idea is to first sort the array, then find sum of first m elements and sum of last m elements. Finally return difference between two sums.
// Java program to find difference
// between max and min sum of array
import java.util.Arrays;
class GFG {
// utility function
static int find_difference(int arr[], int n,int m)
{
int max = 0, min = 0;
// sort array
Arrays.sort(arr);
for (int i = 0, j = n - 1;
i < m; i++, j--) {
min += arr[i];
max += arr[j];
}
return (max - min);
}
// Driver program
public static void main(String arg[])
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
int m = 4;
System.out.print(find_difference(arr, n, m));
}
}
Input : arr[] = 5 8 11 40 15
m = 2 Output : 42 The difference is (40 + 15) - (5 + 8) |
13.check subset sum is available or not
import java.util.*;
import java.io.*;
class GFG
{
static boolean modularSum(int subset[],int n, int m)
{
boolean[][] a=new boolean[n+1][m+1];
int i=0;
int j=0;
for(i=0;i<n;i++)
{
a[i][0]=true;//i m doing zeroth column zero
}
for(i=1;i<=n;i++) //starting from 1 means in last i will write subset i-1
{
for(j=1;j<=m;j++)
{
if(j<subset[i-1])//starting from 1 that's why subset of i-1
{
a[i][j]=a[i-1][j];
}
else
{
a[i][j]=a[i-1][j] || a[i-1][j-arr[i-1]];
}
}
}
return a[n][m];
}
public static void main(String arg[])
{
int arr[] = {1,3,7};
int n = arr.length;
int m = 10;
if(modularSum(arr, n, m))
System.out.print("YES\n");
else
System.out.print("NO\n");
}
}
Example 4:
cutting the rod
Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.
Input:
First line consists of T test cases. First line of every test case consists of N, denoting the size of array. Second line of every test case consists of price of ith length piece.
Output:
Single line output consists of maximum price obtained.
Input:
1
8
1 5 8 9 10 17 17 20
Output:
22
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static int print(int[] a)
{
int[] rod=new int[a.length +1];
rod[0]=0;
for(int i=1;i<=a.length;i++)
{
int max=Integer.MIN_VALUE;
for(int j=0;j<i;j++)
{
max=Math.max(max,a[j] + rod[i-j-1]);
}
rod[i]=max;
}
return rod[a.length];
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int s=sc.nextInt();
int[] a=new int[s];
for(int j=0;j<s;j++)
{
a[j]=sc.nextInt();
}
System.out.println(print(a));
}
}
}
5.longest palindronic substring
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer. //leetcode
class Solution
{
private int lo,maxlen;
public String longestPalindrome(String s)
{
int len=s.length();
if(len<=2)
{
return s;
}
for(int i=0;i<len-1;i++)
{
extrapalindrome(s,i,i);
extrapalindrome(s,i,i+1);
}
return s.substring(lo, lo + maxlen);
}
private void extrapalindrome(String s,int j,int k)
{
while(j>=0 && k<s.length() && s.charAt(j)==s.charAt(k))
{
j--;
k++;
}
if(maxlen<k-j-1)
{
lo=j+1;
maxlen=k-j-1;
}
}
}
////////////////////////////////////////////maximum number of palindrome substring
int count=1;
public int countSubstrings(string s)
{
if(s.length()==0)
{
return 0;
}
for(int i=0;i<s.length();i++)
{
palindrome(s,i,i);
palindrome(s,i,i+1);
}
return count;
}
public void palindrome(String s,int i,int j)
{
while(i>=0 && j<s.length() && s.charAt(i)==s.charAt(j))
{
count++;
i--;
j++;
}
}
6.longest palindromic subsequence
Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
"bbbab"
Output:
4
class Solution
{
public int longestPalindromeSubseq(String s)
{
int[][] dp=new int[s.length()][s.length()];
for(int k=0;k<s.length();k++)
{
for(int i=0,j=k;i<s.length() && j<s.length() ;i++,j++)
{
dp[i][j]=(i==j)?1:s.charAt(i)==s.charAt(j)?dp[i+1][j-1] + 2:Math.max(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][s.length()-1];
}
}
7.0/1 knapsack
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of four lines. The first line consists of N the number of items. The second line consists of W, the maximum capacity of the knapsack. In the next line are N space separated positive integers denoting the values of the N items and in the fourth line are N space separated positive integers denoting the weights of the corresponding items.
Output:
Print the maximum possible value you can get with the given conditions that you can obtain for each test case in a new line.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static void calculate(int[] wt,int[] va,int w)
{
int[][] a=new int[va.length+1][w+1];
for(int i=0;i<=va.length;i++)
{
for(int j=0;j<=w;j++)
{
if(i==0 || j==0)
{
a[i][j]=0;
continue;
}
if(j-wt[i-1]>=0)
{
a[i][j]=Math.max(a[i-1][j],a[i-1][j-wt[i-1]] + va[i-1]);
}
else
{
a[i][j]=a[i-1][j];
}
}
}
System.out.println(a[va.length][w]);
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int n1=sc.nextInt();
int w=sc.nextInt();
int[] wt=new int[n1];
int[] va=new int[n1];
for(int j=0;j<n1;j++)
{
va[j]=sc.nextInt();
}
for(int j=0;j<n1;j++)
{
wt[j]=sc.nextInt();
}
calculate(wt,va,w);
}
}
}
8.minimum no of jump to cover
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static int calculate(int[] ar)
{
int[] jumps=new int[ar.length];
jumps[0]=0;
if(ar.length==0 || ar[0]==0)
{
return -1;
}
for(int i=1;i<ar.length;i++)
{
jumps[i]=Integer.MAX_VALUE;
for(int j=0;j<i;j++)
{
if(i<=j+ar[j] && jumps[j]!=Integer.MAX_VALUE)
{
jumps[i]=Math.min(jumps[i],jumps[j] + 1);
break;
}
}
}
if(jumps[ar.length-1]==Integer.MAX_VALUE)
return -1;
else
return jumps[ar.length-1];
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int a=sc.nextInt();
int[] ar=new int[a];
for(int j=0;j<a;j++)
{
ar[j]=sc.nextInt();
}
System.out.println(calculate(ar));
}
}
}
9.egg problem
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static void calculate(int n,int e)
{
int[][] egg=new int[n+1][e+1];
for(int i=0;i<n+1;i++)
{
egg[i][1]=i; //when n floor and 1 egg
}
for(int i=0;i<e+1;i++)
{
egg[1][i]=1; // when 1 egg and n floor
}
for(int i=2;i<n+1;i++)
{
for(int j=2;j<e+1;j++)
{
egg[i][j]=Integer.MAX_VALUE;
for(int x=1;x<i;x++)
{
int breakcondition=egg[x-1][j-1];
int breaknotconfirm=egg[i-x][j];
int c=Math.max(breakcondition,breaknotconfirm) +1;
if(c<egg[i][j])
{
egg[i][j]=c;
}
}
}
}
System.out.println(egg[n][e]);
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int e=sc.nextInt();
int n1=sc.nextInt();
calculate(n1,e);
}
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static void calculate(int egg,int number)
{
int[][] a=new int[egg+1][number+1];
int c=0;
for(int i=0;i<=number;i++)
{
a[1][i]=i;
}
for(int i=2;i<=egg;i++)
{
for(int j=1;j<=number;j++)
{
a[i][j]=Integer.MAX_VALUE;
for(int k=1;k<=j;k++)
{
c=1+Math.max(a[i-1][k-1],a[i][j-k]);
if(c<a[i][j])
{
a[i][j]=c;
}
}
}
}
System.out.println(a[egg][number]);
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int egg=sc.nextInt();
int number=sc.nextInt();
calculate(egg,number);
}
}
}
10.matrix chain multilication
https://www.youtube.com/watch?v=vgLJZMUfnsU
import java.io.*;
class matrix_chain_multiplication
{
public static void calculate(int[] a)
{
int[][] temp=new int[a.length][a.length];
int q=0;
for(int l=2;l<a.length;l++)
{
for(int i=0;i<a.length-l;i++)
{
int j=i+l;
temp[i][j]=1000;
for(int k=i+1;k<j;k++)
{
q=temp[i][k] + temp[k][j] + a[i]*a[k]*a[j];
if(q<temp[i][j])
{
temp[i][j]=q;
}
}
}
}
System.out.print(temp[0][a.length-1]);
}
public static void main(String[] args)
{
int[] a={1,2,3,4};
calculate(a);
}
}
11.word break problem
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
class Solution
{
public boolean wordBreak(String s, List<String> wordDict)
{
if(s==null ||wordDict==null) return false;
boolean[] dp=new boolean[s.length() +1];
dp[0]=true;
for(int i=1;i<s.length() +1;i++)
{
for(int j=0;j<i;j++)
{
if(dp[j] && wordDict.contains(s.substring(j,i)))
{
dp[i]=true;
continue;
}
}
}
return dp[s.length()];
}
}
14.Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of distinct combinations to reach the given score.
input
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N.
Output:
Print number of ways/combinations to reach the given score.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static int count(int ar)
{
int[] table=new int[ar+1];
table[0]=1;
for(int i=3;i<=ar;i++)
{
table[i]=table[i] + table[i-3];
}
for(int i=5;i<=ar;i++)
{
table[i]=table[i] + table[i-5];
}
for(int i=10;i<=ar;i++)
{
table[i]=table[i] + table[i-10];
}
return table[ar];
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] ar=new int[n];
for(int i=0;i<n;i++)
{
ar[i]=sc.nextInt();
}
for(int i=0;i<n;i++)
{
System.out.println(count(ar[i]));
}
}
}
15.You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Output: 3
Explanation: 11 = 5 + 5 + 1
class Solution {
public int coinChange(int[] coins, int amount)
{
int[] dp = new int[amount+1];
for(int i=1;i<=amount;i++)
{
int min=Integer.MAX_VALUE;
for(int j=0;j<coins.length;j++)
{
if(i>=coins[j] && dp[i-coins[j]]!=-1)
{
min=Math.min(min,dp[i-coins[j]] +1 );
}
}
dp[i]=(min==Integer.MAX_VALUE)?-1:min;
}
return dp[amount];
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static int calculate(int[] coins,int total,Map<Integer,Integer> h1)
{
if(total==0)
{
return 0;
}
if(h1.containsKey(total))
{
return h1.get(total);
}
int min=Integer.MAX_VALUE;
for(int i=0;i<coins.length;i++)
{
if(coins[i]>total)
{
continue;
}
int val=calculate(coins,total-coins[i],h1);
if(val<min)
{
min=val;
}
}
min=(min==Integer.MAX_VALUE)?min:min+1;
h1.put(total,min);
return min;
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
int total=sc.nextInt();
int len=sc.nextInt();
int[] a=new int[len];
for(int j=0;j<len;j++)
{
a[j]=sc.nextInt();
}
Map<Integer,Integer> h1=new HashMap<Integer,Integer>();
int p=calculate(a,total,h1);
if(p==Integer.MAX_VALUE)
{
System.out.println(-1);
}
else
{
System.out.println(p);
}
}
}
}
16.how many ways can we make the change? The order of coins doesn’t matter.
For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int p=0;p<n;p++)
{
int n1=sc.nextInt();
int[] coins=new int[n1];
for(int i=0;i<n1;i++)
{
coins[i]=sc.nextInt(); //coins array
}
int amount=sc.nextInt(); //taking amount as input
int[] combinations=new int[amount + 1];
combinations[0]=1; //initializing first as 1
for(int i=0;i<coins.length;i++) //passing for array of coins
{
for(int j=1;j<amount+1;j++)//passing for 0,1,2,3.. amount
{
if(j>=coins[i])
{
combinations[j]+=combinations[j - coins[i]];
}
}
}
System.out.println(combinations[amount]);//here printing last ele. of array
}
}
}
Comments
Post a Comment