Java

Given an array of n positive integers. Find the sum of the maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order i.e. increasing subsequence. Problem link :- click here Code import java.util.Scanner; public class DynamicProgramming_17 { //Recursion static int maxSumIncreasingSubsequence(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 = arr[index] + maxSumIncreasingSubsequence(arr, index+1, arr[index] ); with_out = maxSumIncreasingSubsequence(arr, index+1, last_num); return Math.max(with, with_out); } //DP static int maxSumIncreasingSubsequence(int[] arr) { int n = arr.length; int dp[] = new int[n]; for(int i=0; i<n; i++) dp...

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); ...

Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase. Problem link :- click here Code import java.util.Arrays; import java.util.Scanner; public class DynamicProgramming_10 { //Brute Force static int longestCommonSubsequence(String str1, String str2) { int n1 = str1.length(); int n2 = str2.length(); int max = 0; for(int k=0; k<n1; k++) { int cur = 0; int index = 0; //to store the index from which we have to start searching for the second character for(int i=k; i<n1; i++) for(int j=index; j<n2; j++) if(str1.charAt(i) == str2.charAt(j) ) { cur++; index = j+1; break; ...

Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of S = { S1, S2, .. , SM } valued coins. Problem link :- click here Code import java.util.Arrays; import java.util.Scanner; public class DynamicProgramming_09 { static int coinChange(int[] coins, int n, int sum) { if(sum == 0) return 1; if(n == 0) return 0; if(sum < 0) return 0; if(sum>0 && n<=0) return 0; return coinChange(coins, n-1, sum) + coinChange(coins, n, sum-coins[n-1]); } static int coinChange1(int[] coins,int n, int sum) { int noWaysOfSum[] = new int[sum+1]; Arrays.fill(noWaysOfSum, 0); noWaysOfSum[0] = 1; for(int i=0; i<n; i++) //For each coin { ...

A top secret message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 You are an FBI agent. You have to determine the total number of ways that message can be decoded. Problem link :- click here Code import java.util.Scanner; // TOTAL DECODING MESSAGES public class DynamicProgramming_07 { static int totalDecodingMessages(String str) { if(str.length() == 0) return 1; if(str.charAt(0) == '0') return Integer.MIN_VALUE; if(str.substring(str.length()-2) == "00") return Integer.MIN_VALUE; return totalDecodingMessages2(str); } //recursion static int totalDecodingMessages1(String str) { int n = str.length(); //Condition 5 if(n == 0) return 1; int a = Integer.parseInt( str.substring...

Given an array of N integers arr[] where each element represents the max number of steps that can be made forward from that element. Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then you cannot move through that element. Problem link :- click here Code import java.util.Scanner; // MINIMUM NUMBER OLF JUMPS public class DynamicProgramming_06 { // Recursion static int minJumps(int arr[], int cur, int last) { if(cur == last) return 0; if(arr[cur] == 0) return -1; if(cur + arr[cur] >= arr.length - 1) return 1; int minJumps = Integer.MAX_VALUE; for(int i=cur+arr[cur]; i<=last && i<=cur+arr[cur]; i++) { int jumps = minJumps(arr, i, last); if(jumps + 1 < minJumps) minJump...

Stickler the thief wants to loot money from a society having n houses in a single line. He is a weird person and follows a certain rule when looting the houses. According to the rule, he will never loot two consecutive houses. At the same time, he wants to maximize the amount he loots. The thief knows which house has what amount of money but is unable to come up with an optimal looting strategy. He asks for your help to find the maximum money he can get if he strictly follows the rule. Each house has a[i]amount of money present in it. Problem link :- click here Code import java.util.Scanner; // STICKLER THIEF public class DynamicProgramming_05 { // Recursion and memoization static int maxLoot(int arr[], int start, int memo[]) { if(start >= arr.length) return 0; if(memo[start] != 0) return memo[start]; int withFirstEle = arr[start] + maxLoot(arr, start+2, memo); ...