# Ride through Dynamic Programming

The flow: For every problem ill write the recursive code and then just the dp formula(in few cases i would also write the initialiazation in case of top down)

// General Tips

In topdown approach the base condition of the recursive solution gets converted into the initialization of the dp. In the memoized solution we initialize the dp with -1 initially and then if the value is present then we return that else we go and calculate the first value first and veryyy importantly store them and then return so that it is available for the next time.

Okay, so let’s dive into the ride!!!

PROBLEMS WITH 0/1 KNAPSACK PARENT

**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`

TC and SC — O(n²)

**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)

}

// DP

`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.`

//sum=odd

`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!`

//similarity with subset sum

`basically this problem says find if there is a subset such that the sum is (TOTAL/2)!!!!`

// code

`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!!!

**Tip**: Same goes if we need to find the number of ways to partition the array into two parts such that there sum is same!!

**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.`

// Idea

`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!

//Code Variation

`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;

This question is one of my fav ❤

**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

//logic

`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;

This is the ending of most of the problems whose parent is 0/1 knapsack!!!

PART 2: UBOUNDED KNAPSACK (PARENT)

`In unbounded knapsack, multiple occurences of a particualar item is allowed, that is there is infinte supply of given items.`

// code variation

Since,we can take the same element any number of times,so even if we take it one time, its still unprocessed bcz there are chances that we will take that element again.

//code variation in dp

`dp[i][i] = dp[i-1][j] || `**dp[i]**[j-wt[i-1]]

//recursive approach

`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`

//intution

`we can have as many cuts of given length hence it is an unbounded knapsack problem.`

//code

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];

//some variation

`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

//code

`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...`

//logic

`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])

//a small catch!!!

`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`

//logic (Recursive)

`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));**

}

//once again memoization

dp[102][102] //let max constraints be 100 and 100

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

}

//dp

`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

}

}

Note: To find its length if we can search for the max element in the last row and then go length steps backward and print it!!(print it from index i-length to length :))

**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.`

//logic

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...//codeint 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'

//logic

`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 knowedit 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 do1+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.`

//logic

`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

//logic

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!?

So,here our part 2, LCS parent gets ended… now lets dive to part 3!

3. MATRIX CHAIN MULTIPLICATION(PARENT)

# 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;

4. DP ON TREES(PARENT)

The next part is coming soon… ill edit again!