Ride through Dynamic Programming

1. 0/1 KNAPSACK

// problem

Given an array of weights and its value along with a capacity. We need to find the maximum profit we can get out of it. The below solution is going to form the base for all the problems from 2-7

2. Subset Sum (Parent Problem: 0/1 Knapsack)

// RECURSIVE

bool is_subset(int nums[],int sum,int n){
if(sum==0)return true;
if(n==0)return false;
if(nums[n-1]>sum)return is_subset(nums,sum,n-1);
return is_subset(nums,sum-nums[n-1],n-1) || is_subset(nums,sum,n-1)
}
int dp[n+1][sum+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=sum;j++{
if(j==0)dp[i][j]=1;
else if(i==0)dp[i][j]=0;
else if(nums[i-1]>j)dp[i][j]=dp[i-1][j];
else dp[i][j]= dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
// dp[n][sum] contains the answer

3. Equal Sum Partition Problem (Parent:Subset sum,Grand Parent:0/1 knapsack)

// problem

equal sum partition problem says that we need to divide the array into two subsets such that the sum of both the subsets are same.
if after adding all the elements if the total is odd then we can never divide the array into two parts such that there sum will be equal!
basically this problem says find if there is a subset such that the sum is (TOTAL/2)!!!!
int total = 0;
for(int i=0;i<n;i++)total += nums[i];
if(total%2==1)return false;
else apply_subset_sum_with_sum_equal_to_total_divide_by_2

4. Count of subsets with given sum (Parent:Subset sum,Grand Parent:0/1 knapsack)

The subset sum problem asked for true/false hence we did or opeartion, now instead of that we can do addition
That is, dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
And yeah we are good to go!!!

5. Minimum Subset Sum Difference

// problem statement

We need to partition the array into two parts such that difference of the sum of the elements of the array is minimum. This questions seems to be misleading and thought provoking but it is indeed very very easy and very very similar to the one which we did previously.
Lets consider two subsets say S1 and S2. Now, if Sum(S1)==Sum(S2), then the difference is minimum and we will get 0! In all other cases Sum(S1) < Sum(S2) or Sum(S2) < Sum(S1). What i want to say is that the sum of one of the halfs will be lesser than the others. We also know that Sum(S1)+Sum(S2)=total
Suppose that Sum(S1)<Sum(S2)---- (1)
Now, Sum(S1) = total - Sum(S2)
Now,what will be the possible values of Sum(S1)?
maximum value of Sum(S1) will be equal to Sum(S2) and then onwards as the value of Sum(S2) increases the value of Sum(S1) will decrease and will eventually have greater differences in their sums.
Hence, finally !!!
We can use subset sum target problem here,we can apply the code of target sum of total/2. If the value at that index is false then the first true value from right side will give the value of Sum(S1) that will have the minimum difference!!!!!!!
Booom!
for(int i=0;i<n;i++)total += nums[i]
int sum = total/2;
for(int i=0;i<=n;i++){
for(int j=0;j<=sum;j++){
if(j==0)dp[i][j]=1;
else if(i==0)dp[i][j]=0;
else if(nums[i]>j)dp[i][j]=dp[i-1][j];
else dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]
}
}
//Now after doing this we can check
int i;
for(i=sum;i>=0;i--)if(dp[n][i])break;
//Now at this point i will have optimal value
//Hence min diff!!!
return total-i;

6. Number of ways to partition the array such that we get minum difference

Same as number of ways to partition the array into two parts just in this case we will use the above code and instead of or we will use addition!!! So that we will return the value at the element i.e. dp[n][found_min_index]!

7. Target Sum with +/- sign

//problem statement

We have been given an array and a target sum. We need to attch a symbol(+/-) before an element such that the resultant of the elements of the array is equal to the target sum. We need to find such number of ways.
for e.g. given an array 1 1 2 3 and target sum of 1
ways are 3
+1 +1 +2 -3
+1 -1 -2 +3
-1 +1 -2 +3
Its like partitioning problem where we can divide the array into two parts such that the difference is of the given element. So, that the rest of the elements can be subtracted and we can get that required sum! Boom we are done!
We know that,
Sum(S1)-Sum(S2)=e; ---(1)
Sum(S1)+Sum(S2)=total; ---(2)
Adding 1 and 2 we get,
2*Sum(S1)=e+total
therefore, Sum(S1)=(e+total)/2;
This tells that if e+total is odd we can direclty return 0;
else we will apply subset sum problem to find the number of subsets with sum of the elements value equal to (e+total)/2;
In unbounded knapsack, multiple occurences of a particualar item is allowed, that is there is infinte supply of given items.
dp[i][i] = dp[i-1][j] || dp[i][j-wt[i-1]]
int max_profit(int wt[],int val[],int nums[],int n,int w){
if(w<=0 || n==0)return 0;
if(wt[n]>w)return max_profit(wt,val,nums,n-1,w);
return max(max_profit(wt,val,nums,n-1,w),max_profit(wt,val,nums,n,w-wt[n]))
}

8. Rod Cutting Problem

//problem

We have been given a rod of length n and we have to cut the rod into pieces possibly 0 such that we can maximise the profit. The profit associated with each length is given at profit[i] where it denotes the profit we can gain if we have a cut of length i
we can have as many cuts of given length hence it is an unbounded knapsack problem.
for length=0, the profit we get=0!
hence,
we will create an array of length n which is total length of the rod and we initialize all of them with 0! Since inititially we can get 0 profit with all the lengths.
NOTE:The best part about these problems is that we can solve them in O(N) space.
So,for every i from 1 to n, we will loop through the entire array and dp[j] = max(dp[j],profit[i]+dp[i-j]) //if j>=i else no changes
dp[n] at the last will hold the max profit!
int n;
cin>>n;
int profit[n+1];
for(int i=1;i<=n;i++)cin>>profit[i];
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
dp[j]=max(dp[j],dp[j-i]+profit[i]);
}
}
return dp[n];
Here we have lengths from 1 to n available but instead of that you may have been given an array of length[n] such that length[i] denotes the permissible length of the rod that can be cut!
changes in the code,
dp[j] = max(dp[j],dp[j-length[i-1]]) //if length[i-1]<j

9. Coin Change Problem (Maximum number of ways)

//problem statement

You have been given n denominations which we can use to form a particular value. We have to find the number of ways such that we can reach to that value using the given denominations.
NOTE: We can use the denominations any number of times
This is same kinda problem where in number of ways of making 0 is choosing no coin so dp[0]=1 while the rest will be initialized to 0.
now for every ith denominaton we have to get the number of ways of making j-den[i-1] value. We can add this value to the current element and we are good to go for finding the number of ways.
Hence,
dp[j] = dp[j] + dp[j-den[i-1]] // if den[i-1]>=j else dp[j]
and dp[n] will give us the number of ways!!!

10. Minimum Number of Coins

//problem statement

In the previous problem we calculated the number of ways, in this problem we need to find that way which yeild minimum number of coins. Hey, not that way but essentially the minumum number of coins...
So, if we have no denominations then there are no ways of making that value except value=0(bcz its 1, i.e. no value). Hence, we will relate to previous one... we will initialize the array with INT_MAX for every i>=1 and <=value, for i=0 dp[i]=1;
Now, we need minimum coins hence,
dp[j] = min(dp[j],dp[j-den[i-1]]+1);
// here we are checking if the current coins are minimum or if i include that denomination will give the minimum.
// by including i mean 1(that coin)+(minimum ways to find that j-den[i-1])
if you initialize with INT_MAX then 1+INT_MAX = INT_MIN! So,please beware while initilizing.We may initilialize with value+1 bcz thats not possible for any denominations to! only if we have a negative denomination :")

PART 3: 11. LONGEST COMMON SUBSEQUENCE(PARENT) [The one with maximum offsprings] Atleast two arrays for sure!

//problem

Finding the length of the longest common subsequence between two the strings
string a,b;
cin>>a>>b;
int n = a.size();
int m = b.size();
int LCS(string a,string b,int n,int m){
if(n==0 || m==0)return 0;
if(a[n-1]==b[m-1])return 1+LCS(a,b,n-1,m-1);
return max(LCS(a,b,n,m-1),LCS(a,b,n-1,m-1));
}
int dp[102][102];
memset(dp,-1,sizeof(dp));
int LCS(string a,string b,int n,int m){
if(n==0 || m==0)return 0;
if(dp[n][m]!=-1)return dp[n][m];
if(a[n-1]==b[m-1])return dp[n][m]=1+LCS(a,b,n-1,m-1);
return dp[n][m]=max(LCS(a,b,n-1,m),LCS(a,b,n,m-1));

}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==0 || j==0)dp[i][j]=0;
if(a[i]==b[j])dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

}
}

12. Longest Common Substring

Here we need to find substring. Now, take the complete analogy from the previous one. There if a[i]!=b[i] we were required to find that do we have more matchings ahead, but in this case we don't have to. Hence, if its not matching then d[i][j]=0, else the same thing!!!!
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==0 || j==0)dp[i][j]=0;
if(a[i]==b[j])dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=0; //here is where game chages

}
}

13. Printing the LCS

In the first question, we did find the length of lcs but here we are required to print the entire LCS.
Firstly, make the dp table of lcs
So, we will start with i=n,j=m;
if(a[i]==b[j])it means that the element was taken in lcs to we will add to our lcs...
else if we need to see where we came from, the left side or from top?
So, the one which is greater is what will give us the way..
so, if(dp[i-1][j] > dp[i][j-1])then we came from top else we came from left...
So, the code will be...
//code
int i=n,j=m;
string ans="";
while(i>0||j>0){
if(a[i]==b[j]){ans += a[i];i--;j--;}
else if(dp[i-1][j] > dp[i][j-1])i--;
else j--;
}
ans = ans.reverse();

cout<<ans<<endl;

14. Shortest Common Super Sequence

//problem

This problem says we need to find such a shortest string such that both a and b strings are subsequences of that string.
say a = 'yell',b='ylp', the shortest can be 'yellp'
We can see that both of them will have same characters which are there is the LCS of both the strings.Hence, length of supersequence is LCS + (n - LCS) + (m - LCS) = n+m-LCS
Now,for printing the supersequence we can do the following,
i=n,j=m;
if(a[i]==b[j]){ //if same taking once
ans += a[i];
i--;j--;
}else{
if(dp[i-1][j] > dp[i][j-1]){ //it came from top so for sure b[j] is // not there but top one can match the // previous one
ans += b[j];j--;
}else{ //reverse goes here
ans += a[i];i--;
}
}
printing reverse of ans will give us the supersequence!!!!

15. Minimum Number Of Insertion and Deletion to convert string a to string b(A smaller version of EDIT DISTANCE)

This is the crazy question and completely relates to the previous one!! So we know that we have common elements equal to LCS. Now, the remaining non-matching elements will be L(a)-LCS. Now, all these elements should be deleted right???? And L(b)-LCS will be again uncommon in b...what will we do in this case, we will add right??insert? So, Total deletion+insertions = L(a)-LCS + L(b)-LCS = L(a)+L(b)-2*LCS!Boom!Its done! :)
Also,if you know edit distance problem, instead of taking 1+max(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]). Since,here replacement is not there, we can do 1+max(dp[i][j-1],dp[i-1][j])

16. Longest Pallindromic Subsequence

//problem

we need to find the length of the longest pallindromic subsequence.
This is a really cool problem. So, what we can do is if lets say a[i] == a[j], what we had to do was check whats the length of the longest pallindromic subsequence that can be formed within i+1 and j-1. So, the main idea is to store the length for smaller ranges and then use it for longer ones... for we will start with range=1 and then finally our range will be equal to array length and that is where we will get the longest pallindromic subsequnce length for the entire array.
So,
dp[n+1][n+1];
for(int i=1;i<=n;i++)dp[i][i]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<n-i;j++){
if(a[j]==a[j+i-1])i==2 ? dp[i][j]=2 : dp[i][j]=2+dp[i+1][j-1];
else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
}
}
dp[1][n] will have max value...

17. Longest Repeating Subsequence

//question

We need to find a longest sequence which repeats itslef.. for e.g.
a
a b e b c d d
a a b e b c d d
The bold letters signify the sequence
Its like finding the LCS between the same string just that the elements taken in first string should not be taken in second string.
i.e. it is same as finding the LCS of string a with string a such that when a[i]==a[j] we should make sure that i!=j and thats it!
if(a[i]==a[j] && i!=j )dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

18. Sequence Pattern Matching

given string a we need to find whether string a is a subsequence of string b! Mind you, this is the only offstring which has O(N) TC
what if we can do is we can start with i=0 pointing to string a and j=0 pointing to string b, if a[i]==b[j] then we can move i ahead, whenever we get same letters, we are good to go ahead... we don't need to think abt it again..
So,
int i=0,j=0;
while(i<n && j<m){
if(a[i]==b[j])i++;
j++
}
if(i==n)return true;
else return false;

19. Minimum Number Of Insertion/Deletion to make pallindrome

Okay so again here we can find LPS, and that is already pallindrome right!?
So, rest of elements can either be deleted or its pair can be added... So, minimum number of insertions/deletions = L(s)-L(LPS)
Wasn't it great!?

20. MCM

//problem

//dp[1001][1001]
//memset(dp,-1,sizeof(dp))
int solve(int a[],int i,int j){
if(i>=j)return 0;
int ans = INT_MAX;
for(int k=i;k<j;k++){
if(dp[i][k]!=-1)dp[i][k]=solve(a,i,k);
if(dp[k+1][j-1]!=-1)dp[k+1][j]=solve(a,k+1,j-1);
int temp_ans = dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j];
ans = min(ans,temp_ans);
}
}
return ans;

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
YashTailor

YashTailor

7 Followers

MEVN || Android Studio || Competitive Programmer || BS4