Dp Learnings (27 Part Series)
1 House Robber leetcode problem
2 Jump game leetcode problem
… 23 more parts…
3 Jump game II leetcode problem
4 Cherry Pickup II Leetcode Problem
5 Partition Equals Subset Sum Leetcode problem or Subset sum equals to target
6 Maximum Sum Problem GeeksForGeeks
7 Count Palindrome Sub-Strings of a String GeeksForGeeks
8 Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode
9 0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded
10 Shortest distance from source to all other nodes in a Directed Acyclic Graph
11 Coin change Leetcode
12 Coin Change 2 Leetcode
13 Target Sum or Partition with given difference Leetcode
14 Rod cutting Problem (similar to unbounded knapsack)
15 Length of longest common substring
16 Longest Palindromic subsequence (Same as Lcs)
17 Minimum Insertion steps needed to make a string palindrome (Same as LCS)
18 Minimum number of Insertion and deletion needed to convert String A to String B or make both the strings equal (same as lcs)
19 Shortest Common Super-sequence Leetcode (Same as Lcs string)
20 Distinct Subsequence Leetcode
21 Partition with given difference
22 Two best non overlapping events
23 Longest increasing subsequence
24 Edit distance
25 Maximum product subarray
26 Target sum
27 Maximum Multiplication Score
Given an array ‘ARR’, partition it into two subsets (possibly empty) such that their union is the original array. Let the sum of the elements of these two subsets be ‘S1’ and ‘S2’.
Given a difference ‘D’, count the number of partitions in which ‘S1’ is greater than or equal to ‘S2’ and the difference between ‘S1’ and ‘S2’ is equal to ‘D’. Since the answer may be too large, return it modulo ‘10^9 + 7’.
If ‘Pi_Sj’ denotes the Subset ‘j’ for Partition ‘i’. Then, two partitions P1 and P2 are considered different if:
Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 50
0 ≤ D ≤ 2500
0 ≤ ARR[i] ≤ 50
Enter fullscreen mode Exit fullscreen mode
Recursive solution:
It will lead to TLE as its not optimal
import java.util.*;
public class Solution {
static int mod = (int)(1e9+7);
public static int countPartitions(int n, int d, int[] arr) {
// Write your code here.
/* given : 1. s1 + s2 = sum; where sum is sum of all the elements in the array 2. s1-s2 = D for s1>s2; modifications: since s1+s2 = sum;hence s1 = sum-s2; from 2, sum-s2-s2 = D; ie s2 = (sum-D)/2 = target; so we have to find all the subsets that are equal to target :) edge cases to avoid : 1. (sum-D)/2 can't be fraction value hence (sum-D) should be even 2. (sum-D)>=0 since it can't be nagative as sum of all the elements of the array can't be negative */
int target =0;
for(int i : arr) target+=i;
//implementing edge case first
if(target-d<0 || (target-d)%2!=0) return 0;
return findSubsetSumCountEqualsToTarget(arr,n-1,(target-d)/2);
}
public static int findSubsetSumCountEqualsToTarget(int [] arr, int i, int target){
if(i==0){
//since 0<=arr[i]<=50; hence we have to check the possibility of 0 as well
// if arr[i]==0 and target =0 then you should return 2
//as there are two solutions now ie either you will take this 0 or won't take this 0
//in either case of taking or not taking of 0 target will remain 0 only, as 0 won't alter target value hence there will be 2 possible solutions
if(target ==0 && arr[i]==0) return 2; // extra line added to the usual appraoch because of presence of 0 in the array
if(target==0 || arr[i]==target) return 1; // usual approach
return 0;
}
int left =0;
if(target>=arr[i]){
left = findSubsetSumCountEqualsToTarget(arr,i-1,target-arr[i]);
}
int right = findSubsetSumCountEqualsToTarget(arr,i-1,target);
return (left+right)%mod;
}
Enter fullscreen mode Exit fullscreen mode
Dp Memoization solution:
//create dp array in the driver class , and add dp to the function call
int dp[][] = new int[n][(target-d)/2 +1] ;
for(int row[]: dp) Arrays.fill(row,-1);
Enter fullscreen mode Exit fullscreen mode
public static int findSubsetSumCountEqualsToTarget(int [] arr, int i, int target,int dp[][]){
if(i==0){
//since 0<=arr[i]<=50; hence we have to check the possibility of 0 as well
// if arr[i]==0 and target =0 then you should return 2
//as there are two solutions now ie either you will take this 0 or won't take this 0
//in either case of taking or not taking of 0 target will remain 0 only, as 0 won't alter target value hence there will be 2 possible solutions
if(target ==0 && arr[i]==0) return 2; // extra line added to the usual appraoch because of presence of 0 in the array
if(target==0 || arr[i]==target) return 1; // usual approach
return 0;
}
if(dp[i][target]!=-1) return dp[i][target];
int left =0;
if(target>=arr[i]){
left = findSubsetSumCountEqualsToTarget(arr,i-1,target-arr[i],dp);
}
int right = findSubsetSumCountEqualsToTarget(arr,i-1,target,dp);
return dp[i][target] = (left+right)%mod;
}
}
Enter fullscreen mode Exit fullscreen mode
Tabulation:
import java.util.*;
public class Solution {
static int mod = (int)(1e9+7);
public static int countPartitions(int n, int d, int[] arr) {
// Write your code here.
/* given : 1. s1 + s2 = sum; where sum is sum of all the elements in the array 2. s1-s2 = D for s1>s2; modifications: since s1+s2 = sum;hence s1 = sum-s2; from 2, sum-s2-s2 = D; ie s2 = (sum-D)/2 = target; so we have to find all the subsets that are equal to target :) edge cases to avoid : 1. (sum-D)/2 can't be fraction value hence (sum-D) should be even 2. (sum-D)>=0 since it can't be nagative as sum of all the elements of the array can't be negative */
int target =0;
for(int i : arr) target+=i;
//implementing edge case first
if(target-d<0 || (target-d)%2!=0) return 0;
return findSolByTabulation(arr,n,(target-d)/2);
}
public static int findSolByTabulation(int [] arr, int n, int target){
int dp[][] = new int[n][target +1] ;
for(int row[]: dp) Arrays.fill(row,-1);
if(arr[0] ==0) dp[0][0] = 2;
else dp[0][0] = 1;
if(arr[0]!=0 && arr[0]<=target) dp[0][arr[0]]=1;
for(int i =1;i<arr.length;i++){
for(int tar = 0;tar<=target;tar++){
int left =0;
if(tar>=arr[i]){
left = dp[i-1][tar-arr[i]];
}
int right = dp[i-1][tar];
dp[i][tar] = (left+right);
}
}
return dp[n-1][target];
}
}
Enter fullscreen mode Exit fullscreen mode
Dp Learnings (27 Part Series)
1 House Robber leetcode problem
2 Jump game leetcode problem
… 23 more parts…
3 Jump game II leetcode problem
4 Cherry Pickup II Leetcode Problem
5 Partition Equals Subset Sum Leetcode problem or Subset sum equals to target
6 Maximum Sum Problem GeeksForGeeks
7 Count Palindrome Sub-Strings of a String GeeksForGeeks
8 Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode
9 0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded
10 Shortest distance from source to all other nodes in a Directed Acyclic Graph
11 Coin change Leetcode
12 Coin Change 2 Leetcode
13 Target Sum or Partition with given difference Leetcode
14 Rod cutting Problem (similar to unbounded knapsack)
15 Length of longest common substring
16 Longest Palindromic subsequence (Same as Lcs)
17 Minimum Insertion steps needed to make a string palindrome (Same as LCS)
18 Minimum number of Insertion and deletion needed to convert String A to String B or make both the strings equal (same as lcs)
19 Shortest Common Super-sequence Leetcode (Same as Lcs string)
20 Distinct Subsequence Leetcode
21 Partition with given difference
22 Two best non overlapping events
23 Longest increasing subsequence
24 Edit distance
25 Maximum product subarray
26 Target sum
27 Maximum Multiplication Score
暂无评论内容