Java

Given an array of integers, find the length of the longest (strictly) increasing subsequence from the given array. Problem link :- click here Code import java.util.Arrays; import java.util.Scanner; public class DynamicProgramming_16 { //Recursion static int longestIncreasingSubsequence(int[] arr, int index, int last_num) { if(index >= arr.length) return 0; int with = 0, with_out = 0; if(arr[index] > last_num) with = 1 + longestIncreasingSubsequence(arr, index+1, arr[index]); with_out = longestIncreasingSubsequence(arr, index+1, last_num); return Math.max(with, with_out); } //DP //Here we have store value w.r.t index and last_num static int longestIncreasingSubsequence1(int[] arr) { int n = arr.length; int dp[] = new int[n]; Arrays.fill(dp, 1); i...

Rahul and Ankit are the only two waiters in the Royal Restaurant. Today, the restaurant received n orders. The amount of tips may differ when handled by different waiters, if Rahul takes the ith order, he would be tipped ai rupees and if Ankit takes this order, the tip would be bi rupees. In order to maximize the total tip value they decided to distribute the order among themselves. One order will be handled by one person only. Also, due to time constraints Rahul cannot take more than x orders and Ankit cannot take more than y orders. It is guaranteed that x + y is greater than or equal to n, which means that all the orders can be handled by either Rahul or Ankit. Find out the maximum possible amount of total tip money after processing all the orders. Problem link :- click here Code import java.util.HashMap; import java.util.Scanner; public class DynamicProgramming_15 { //Recursion static int maxTip(int n, int a[], int b[], int x, int y) { if(n ==...

There is a stack of water glasses in a form of pascal triangle and a person wants to pour the water at the topmost glass, but the capacity of each glass is 1 unit. Overflow takes place in such a way that after 1 unit, 1/2 of remaining unit gets into bottom left glass and other half in bottom right glass.Now John pours K units of water in the topmost glass and wants to know how much water is there in the Cth glass of the Rth row. Problem link :- click here Code import java.util.Arrays; import java.util.Scanner; public class DynamicProgramming_14 { static void fill(float k, int r, int c, float pyramid[][]) { if(r >= pyramid.length) return; pyramid[r][c] += k; float rem = 0; if(pyramid[r][c] > 1) { rem = pyramid[r][c] - 1; pyramid[r][c] = 1; fill(rem/2, r+1, c, pyramid); fill(rem/2, r+1, c+1, py...

Given a rod of length N inches and an array of prices, price[] 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. Problem link :- click here Code import java.util.Scanner; public class DynamicProgramming_13 { //Recursion and Memoization static int maxAmount(int price[], int n, int memo[]) { if(memo[n] != 0) return memo[n]; if(n==0 || n==1) return price[n]; int max = 0; int cur = 0; for(int i=1; i<=n; i++) { cur = price[i] + maxAmount(price, n-i, memo); if(cur > max) max = cur; } memo[n] = max; return max; } //DP static int maxAmount1(int price[], int n) { int dp_arr[] = new int[n+1]; for(int i...

Given two strings s and t. Return the minimum number of operations required to convert s to t. The possible operations are permitted:   1. Insert a character at any position of the string.  2. Remove any character from the string.  3. Replace any character from the string with any other character. Problem link :- click here Code import java.util.Scanner; public class DynamicProgramming_12 { //Recursion static int noOfOperations(String str1, String str2) { int n1 = str1.length(); int n2 = str2.length(); if(n1==0 && n2==0) return 0; if(n1==0 && n2>0) return n2; if(n1>0 && n2==0) return n1; if( str1.charAt(0) == str2.charAt(0) ) return noOfOperations(str1.substring(1), str2.substring(1)); else { //Operations are done for str...

Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s. Problem link :- click here Code import java.util.Arrays; import java.util.Scanner; public class DynamicProgramming_11 { //Recursion and Memoization static int noConsecutive1s(int n, int[] memo) { if(memo[n] != 0) return memo[n]; if(n == 1) { memo[n] = 2; return 2; // 0 & 1 } if(n == 2) { memo[n] = 3; return 3; // 00 & 01 & 10 } int start_10 = noConsecutive1s(n-2, memo); int start_0 = noConsecutive1s(n-1, memo); return start_10 + start_0; } //DP static int noConsecutive1s1(int n) { int arr[] = new int[n+1]; Arrays.fill(arr, 0); ...