Dynamic Programming

Question 1

Longest common subsequence

Answer 1

Dp[m+1][n+1]
First row and first column 0 as empty string
Check if last characters match. If they match then dp[i][j]= dp[i-1][j-1]
Else
You have two options. You can check lcs with whole of string 1 and string2 upto last but one char and vice versa.
Dp[i][j]=max(dp(i-1,j) dp(i,j-1)

Return dp(m,n)

Question 2

Coin change

Given an array of coin types we need to find out the total possible ways of getting the given sum

Answer 2

We have to choices. Either we include the last coin or we don’t. We can include it only if it’s value is less than sum
Dp(sum+1, n+1)
So when we don’t include
Dp(i,j)=dp(i, j-1)
Additionally if value is les than sum we can include it
Dp(i,j)+= dp(i-coins(j),j)
J and not j-1 cause repetitions of coins are allowed.

Return dp(sum, n)

Question 3

Edit distance
Given two strings S1 nd S2, find the minimum number of operations to convert S1 to S2
Insert, del, replace

Answer 3

Dp(m+1, n+1)
Base cases if i=0 or j=0, return j and i resp
Else
If last char match, then dp(i,j)= dp(i-1, j-1)
Else
We will do one operation. So +1
Replace m-1, n-1
Del m-1, n
Insert m, n-1
So dp(i,j) =1+ min( dp(i-1,j-1), dp(i-1, j), dp(i,j-1))

Question 4

Longest increasing subsequence

Answer 4

The idea is to find lis of subsequence ending with the current element

Inc order n
Dec order 1

Lis(0)=0
For i =1 to n-1
We are sunbsequences ending with i
  For j  from0 to i-1
   If arr[j]< arr[i] 
   Then lis(i)= max(lis(j)+1, lis(i))

Now traverse through whole of lis array and find the max and return it

Why j is needed
If we do not consider j and just do lis(i) = lis(i-1)+1 we would be considering only those subsequences which end with arr(i-1) as well

Question 5

0-1 Knapsack problem
Given an array of weights and another array of values, and Knapsack cap, we have to find max value such that the total weight doesn’t exceed knapsack capacity.

Answer 5

Dp(n+1,w+1)
Dp(i,j) is Max value which can be obtained with first i items and with knapsack cap j

Again, consider the last item
We have two cases. If it’s weight is more than cap, then we can’t consider it dp(i,j)=dp(i-1,j)
Else even now we have the option of either considering it or not and we choose whatever is Max
Dp(i,j) is Max(dp(i-1,j) , dp(i-1, j-wt(i))+Val(i-1))

Question 6

Optimal strategy for game
Given even number of coins, you and your opponent can pick only corner coins. How can you make sure that you will always win?

Answer 6

We want the func to return our value.
How do we return our value when the opponent call the func? Opponent will chose his maximum and gives us a minimum value.

Base case, if there are only two values, return the max of the two

Dp[n][n]
For i from 0 to n-1
Dp(i,i+1)=max(arr(i),arr(i+1))

I is start index and j is end index. I>j
So we don’t have to fill lower half of the dp table.
We have two choices.
First pick ith coin. Opponent will have 2 cases either i+1 . In that case return us i+2 to j or he picks j, and returns us i+1 to j-1
Arr[i] +min(dp(i+2,j), dp(i+1, j-1)
Or we pick j
Arr(j) + min(dp(i+1,j-1) , dp(i,j-2))
Dp(i,j) will be max of these two

Final ans will be at dp(0,n-1)

Question 7

Minimum deletions to make an array sorted

Answer 7

N-lis

Question 8

Maximum sum increasing subsequence

Out of all increasing subsequences we need to find the one with max sum

Answer 8

Same as lis, instead of just storing the max length in lis array, we store the sum
Lis(i)=arr(i)
For j from 0 to i
Lis(i)= max( lis(j)+arr(i), lis(i))

And then traverse through lis array and find the maximum

Question 9

Maximum length of bitonic subsequence

Bitonic sequence is one which first increases and then decreases.

Answer 9

We find the longest increasing subsequence ending with every element. That gives us the increasing part upto the pivot element. Now we need to find the length of the longest decreasing subsequence that begins with every element. For this LDS we have to traverse from right.

Max(lis(i)+LDS(i)+1) is the ans

Question 10

Building bridges
Maximize the number of bridges we can build, such that no two of them cross.
You are given a list of bridges with their start and end points on two sides of the river

Answer 10

First sort all pairs in increasing order of first value
If two first values are same then consider second value
Find lis of sorted array according to second value

Starting points are already sorted. If the ending points are also in increasing order then there won’t be any crosses. So we cal lis which is nothing but longest increasing subsequence

Question 11

Longest chain of pairs

Given a list of pairs where in each pair a<b></b>

Answer 11

Sort the array in the increasing order of first value

Now find lis with the only change that arr(i).first > arr(j).second in lis condition

Question 12

Minimum insertions and deletions to convert S1 to S2

Answer 12

Find lcs of S1 and S2
S1 length m
S2 length n
Lcs l
M-l deletions 
N-l insertions
M+n-2l

Question 13

Shortest common supersequence

Given two strings, we have to find a third string containing the two and is the shortest

Answer 13

Once we have lcs we traverse the first string and insert extra characters in order. And then traverse the second and insert the extra char

Need printing or storing of lcs

Question 14

Longest palindromic subsequence

Answer 14

To find longest palindromic subsequence we have to reverse the given string to get S2. Then the length of longest palindromic subsequence is nothing but lcs of S1 and S2

Question 15

Longest repeating subsequence

Answer 15

Same as lcs but with an additional condition that last char match and their indexes are not the same

Question 16

Printing lcs

Answer 16

We can use our 2 d array to print the actual lcs. We can traverse the 2 d array from bottommost right most corner and whenever we see matching char, we move along the diagonal and print. Else we take maximum of upper and lower and in this case we don’t print the char

Question 17

Minimum jumps to reach end

Given an array where every elements represents the max number of jumps that can be made from that point in the array

Answer 17

Greedy solution will not work.
We have to traverse from back and see from where we can reach end
Then num of jumps will be 1+ the number of jumps to reach that position.
The minimum possible such answer is what we want

For i from 0 to n-1
For j from 0 to i 
If (arr(j)+j>=i)
 If(dp(i) not equal to int_max
    Then dp(i) =min(dp(i), dp(j)+1)

Question 18

Min coins to make a value, given infinite supply of every coin type in the set

Answer 18

Dp[Val+1]
Dp[0]=0
Initially dp array is infinite
For int i=1 to Val
 For j from 0 to n
   If(arr(j)<i></i>

Question 19

Egg dropping puzzle

Find the minimum number of egg dropping trials needed to find the threshold floor

Answer 19

At a given floor there are two cases. Either the egg breaks or it doesn’t.
If the egg breaks we will have to check for all floors below. If it doesn’t, we will have to check for thresholds above this current floor

Res(f,e)= min( max(breaks, doesn’t break))
Min because we want the minimum floor and maximum because we consider the worst case possibility from the current floor.

Res(f,e) =min(max(res(x-1,e-1), res(f-x,e))+1

Base cases res(f,1)=f
Res(0,e)=0
Res(1,e)=1

Dp[f+1][e+1]
Fill first row with zero as f is 0
Similarly fill second column with i as number of eggs is 1 as you will try from below
Now for every other value i, j,. I representing floor and j the number of eggs
Dp(i,j)=int_max
For (x=1, x<=i; x++)
Dp(i,j)=min(dp(i,j), max(dp(x-1,j-1),dp(f-x, j))

Return dp(f,e)

Question 20

Count BST
Given a number n, we have to consider n distinct keys and count the number of unique bsts we can make from those keys. The value of keys doesn’t matter

Answer 20

Say n is 5

1 2 3 4 5
We can consider 1 as root. Then 0 elements on left and n-i-1 elements on right. Next 2 as root and so on..

Res(n)= sum from i=0 to n-1
Res(i)*res(n-i-1)
This is the logic

Dp[n+1]
For int i=1 to n
 Dp(i)=0
  For j from 0 to i
  Dp(i)+= dp(j)*dp(i-j-1)

Return dp(n)

Question 21

Maximum sum with no 2 consecutives

Answer 21

Again considering from last element

There are two cases. You either consider this element or you don’t. If you consider you can’t consider the element before it
Dp(i)=max( dp(i-2)+arr(i), dp(i-1))

Can be space optimised as we do not need the entire dp array. We only need prev and prev_prev

Question 22

Number of subsets with given sum

Answer 22

dp[n][sum]
We begin from the lasst element. We either include it or not
If arr(n-1) > sum then only one case .
Don’t include return count (sum, n-1)
Need to check the above condition first to ensure that the sum is not negative. Cause in dp index cannot be negative.
Else (count(sum,n-1) + count( sum-arr(n-1), n-1))

Question 23

Matrix chain multiplication
Given an array of size n which represents n-1 matrices, find the minimum num of element multiplications needed to multiply all of them together

Answer 23

To multiply matrices of size (i,j) (j,k) we need jik number of multiplications.
Now we can make the first partition in number of ways from index 1 to n-1.
Dp[n][n]
Dp(i,j) stores the result for subarray from index i to j
We cannot just fill the dp array row wise. We use gap method where we fill diagonally
Base case when I+1=j meaning only one matrix, for that we don’t have to multiply. So 0
For (i from 0 to n-1)
Dp(i,i+1)=0
For (int gap=2 gap less n, gap++)
For (i from 0 to gap+i less then n)
J =i+gap
For k from i+1 to j
Dp(i,j)=min(dp(i,j), dp(i,k)+dp(k,j)+ arr(i)arr(j)arr(k))

Return dp(0,n-1)

Question 24

Palindrome partitioning

Given a string we have to make minimum cuts in the string so that all parts are palindromic

Answer 24

If our string is already palindrome we return 0 this is one of the base case.
If the string is not palindrome, then we need to make some partitions.
We try making our first partition in all possible places and recursively call on the left and right partitions and add 1. When we make the first partition in all possible ways, we track the min and return the minimum of all answers.

Dp(i,j) stores the min cuts required for the substring i to j
Since dp array dimensions correspond to start and end index, we follow gap method.
Lower half not needed as start index is always greater than end index

For  gap from 1 to n
 For i from 0 to gap+i less than n
 J= gap+i
 Firstly check if it is palindrome
  Dp(i,j)=0
Else
 Dp(i,j)=inf
 For k=1 to j
 Dp(i,j)= min(dp(i,j), 1+dp(i,k)+dp(k+1,j)

Ret dp(0,n-1)

Question 25

Allocate min pages
Given number of pages in n books, and k students who are supposed to read all the books, we need to minimise the maximum number of pages that can be alloted under the constraint that only continuous pages can be alloted to a student

Answer 25

We need to choose k-1 cuts out of n-1 cuts.
We can choose any of the n-1 cuts as our first cuts and assign one side to one student and the other part to k-1 students

For every possible first partition
Res=min(res, max( sum(arr,i n-1) ,minpages(arr, i ,k-1))
Sum is how many pages will that one student read and we want maximum as we want max pages.
We use min as we need to minimise the maximum pages for every possible first partition.

Dp(n,k)
Dp(i,j) is min of max pages with i people and j books
Dp(1,i) is sum as only one student
Dp(i,1) = arr(0) 
For i from 2 to k
  For j from 2 to n
    Int res =inf
For p from i+1 to j
Res=min( res, max(dp(i-1,p), sum(arr,p,j-1))
Dp(i,j) =res

Ret dp(k,n)

Question 26

Maximum cuts
Given a rod of length n and 3 values a,b,c, we want to make maximum cuts in this rod such that length of every cut should be either a b or c.

Answer 26

Dp(n+1)
Dp(0)=0
For i from 1 to n
Dp(i)=-1
 If i-a >0 then dp(i)=max(dp(i), dp(i-a))
 Similarly for b and c
If dp(i) not equal to -1 dp(i)++

Return d(n)

Question 27

Scrambled strings
Given a string a we can represent it as a bt, partitioning it into 2 non empty substrings recursively. To scramble a string we choose any non leaf node and swap it’s 2 children.
Given two strings a and b of same length determine if b is a scrambled string of a.

Answer 27

We use a map to keep track of cases we have already visited
Base case if both the strings are equal , return map of S1+#+S2 as true.
If size is one and not equal, they cannot be scrambled counterparts.
So return map of S1+#+s2 false
If we have already visited this case then return the ans stored.
We can make the first partition in any of the positions from 1- n-1

We have 2 cases
Case 1: when we check blocks 1 of both S1 and S2 and blocks 2 of both S1 and S2.:if they match then yes, they are scrambled counterparts.

Bool cond1

Case 2 when we check block 1 of S1 and block 2 of S2 and block 2 of S1 and block 1 of S2.

If either condition 1 or 2 is true we return map of S1+#+S2 as true

Else false

Question 28

Distinct sequences

Given two sequences a and b cunt number of unique ways in sequence a to form a subsequence that is identical to b

Answer 28

Choices(s,t,n,m, i,j)
Base cases when j ==m ret1. While string t has been processed and we have an answer
If i==n ret 0 if s becomes empty string then we cannot achieve ans
If the first chat match, then we have 2 choices. We can either consider the first chat or not. If we consider then we increase both i and j. If we don’t, then we increase i but not j.
If the first char do not match, the we have only one choice of not including it i+1, j

In dp solution we do the same thin in a bottom up manner
Dp(m,n)
If ast char match, 
Dp(i,j)= Dp(i-1,j-1)+dp(i-1,j)
Else 
Dp(i,j) =dp(i-1,j)

Return dp(m,n)

Question 29

Smallest sequence with given primes

Given 3 prime numbers a, b and c and an integer d, you have to find the first smallest inter

Answer 29

Dp(0)=0
Int P1=0, int P2=0 P3 also 0
For i from 0 to d
 A_mul= dp(P1)*a
 Similarly b and c
 Dp(i) is min of these 
Increment the pointer of that min

Question 30

Tiling 3A board with 21 dominoes

Find the minimum number of ways to fill the board

Answer 30

An=An-2 +2*(bn-1)

Bn= an-1+ bn-2

Question 31

Paint houses
There are a row of n houses, each house can be painted with one of the three colours. You have to paint all the houses such that no two adjecent house have the same colour. The cost of painting each house with a certain colour is represented by a n*3 matrix. Find the minimum total cost to paint all houses

Answer 31

In the dp array of n*3 we only need the previous row while computing the current row. So for space optimization, we only maintain the prev row.
Initially prev(0) = A(0)
For i from 1 to n
Next(0) =min(prev(1)+a(i,0), prev(2)+a(i,0))
If we paint the current hous with color 0 then the min cost is min cost upto n-1 houses with color other than 0 and the to cost to paint the current house with color 0.
Similarly next(1) and next(2)
Prev = next
Return min of next(1), next(2), next(3)

Question 32

Number of ways to decode

A-Z are mapped from 1-26. Given a message containing only numbers, determine the total number of ways to decode it.

Answer 32

If the current element is btw 1-9 you can decode it as is.
Dp(i)=dp(i-1)
If additionally, the prev element is 1 or 2 , you can decode it combined also.
If s(i-2)==1
Dp(i)+=dp(i-2)
Else if s(i-2) ==2 and s(i-1) btw 1&6
Dp(i)+=dp(i-2)

Question 33

You are climbing a staircase and it takes A steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Answer 33

Dp(i)=dp(i-1)+dp(i-2)

Space optimization by maintaining prev and prev_prev

Question 34

Intersecting chords in a circle
Given a number A return the number of ways you can draw A chords in a circle with 2A points such that no 2 of them intersect.

Answer 34

Dp(2A+1)
The idea is to first consider points on the left side of the first chord, remaining n-j points on the right and recursively call the function on left and right sides. For odd numbers the ans will be zero as one point will be remaining and to make that a chord it will cross both the sides.
Dp(0)=1
Dp(2)=1
For i from 4 to 2A for even numbers
 Dp(i)=0
 For j from 0 to i-2
 (No. of ways to make the first partition )
 Dp(i)+=dp(j) +dp(i-j-2)

Return dp(2A)

Question 35

Jump game array
Given an array of non negative integers, you are intially positioned at the 0th index of the array. Each element of the array represents the max jump length at that position. Determine if you are able to reach the last index

Answer 35

Intially reach is 0
For i from 0 to n-1
If reach less than i
 Return 0
Else reach is Max (reach, arr(i)+i)

Return 1

Question 36

Longest Arithmetic Progression

Find longest AP in an integer array of size N and return it’s length

Answer 36

If size is less than or equal to 2 , return size
Intialize maxlen as 2
First sort the array so that we do binary search
Dp(n,n)
Dp(i,j) will have the length of the longest AP with i as first element and j as second element. If i j and k are in ap, then i+k=2j. If less then k++ else i–
Last column will be all 2s
Fixing j
For j from n-2 to 1
I=j-1 and k=j+1
While i>0 and k=0 we make dp(i, j) =2

Return maxlen

Question 37

N digit numbers with digit sum S

Find out the number of N digit numbers whose digits on being added equals to s. Leading zeros not allowed

Answer 37

If n is 0 and sum is 0 return 1
If n is 0 or sum is 0 return 0
If 9*n less than sum, return 0

If dp(n,sum)!=-1 return that
Res=0
For i from 0 to 9
 If n==1 and i is 0 continue as leading zeros
If sum>i 
 If f(n-1, sum-i,dp)
   Res+= f(n-1, sum-i,dp)
Else break

Return dp(n,sum)

Question 38

Best time to buy and sell stocks atmost B times. Find maximum profit you can achieve

Answer 38

Dp array has number of transactions as rows and different days as columns. Number of transactions vary from 0-b. So of size b+1

Dp(b+1,n)
Dp(0,i)=0
Dp(i,0)=0
For b=0 profit will be zero. For day 0 profit will again be zero as we can only buy but not sell on the first day itself.
For i from 1 to B
  Var= -A(0)+ dp(i-1,0)
  For j from 1 to n

At day j we have 2 options.we can either sell and make the ith transaction or choose not to sell. If we don’t sell then out ans is same as i transactions upto day j-1 dp(i,j-1)

But if we choose to sell on that day we need to find the best day to have bought the stock for the ith transaction. For this we traverse all days before j and choose the one which gives best overall profit and not just for ith transaction.
For everyday we are traversing we cal what is the previous profit upto i-1 + current profit or loss.
For k from 1 to j
Var= max(var, -A(k)+ dp(i-1,k)
Dp(i,j) = max of chose to sell and chose not to sell
Dp(i,j)= max(var+A(j), dp(i,j-1)
Var=max(car, -A(j)+dp(i-1,j)

Return dp(b, n-1)

Question 39

Evaluate expression to true

Given an expression A with operands and operators and or xor, in how many ways can we evaluate the expression to true

Answer 39

F(i, j, is true, exp)
If  i>j return 0
 If i=j if isTrue ret exp(i)==T
          Else return exp(i)==F
If dp(i,j, isTrue) !=1 return stored ans
Int ways=0
We can make the first partition from i+1 to j-1
Lt is no. Of ways of eval left exp to t
Similarly lf, rt, rf

If exp(idx) is and 
 Then if isTrue both should be true
  Else lt,rf+lf,rt+lf,rf
If operator is or
 If isTrue the way+= lt,rf+lf,rt + rt,lt
Else ways+= lf, rf

Similarly consider cases for for
 Return Dp(i,j, isTrue)=ways

Question 40

Maximum sum path in BT

Answer 40

If not A ret 0
Int left =maximum sumpath(A-left, ans)
Similarly right
Straight_path= max(a, max(a+left, a+right))
Curved path= a+left+right
Cannot take curved paths forward
Ans=max(ans, straight path, curved path)
Return straight path

Question 41

Kingdom wars

Find the maximum sum submatrix

Answer 41

Dp(n+1,m+1)
Int ans=int_min
For i from n to 0
For j from m to 0
 If i or j is m or n cont
 Dp(i,j)=a(i,j)+dp(i+1,j)+dp(i,j+1)-dp(i+1,j+1)
Ans=max(ans,dp(i,j))
Return ans

Question 42

Maximum size square sub matrix

Given a 2 D binary matrix of size nxm, find the area off maximum size square submatrix will all 1s

Answer 42

Dp(m,n)={0}
Dp(i,j) contains the maximal possible square submatrix ending at that cell.
Because for construction of n sized square subarray, we would need 3 previous nebors to aslo be one.

In doing so we are not assuming that the subarray will always start at 0,0
because when min of all of them is zero, it means we are considering sole square call ati,j which could be the starting point of someother subarray
ans=0
For i from 0 to m
For j from 0 to n
If i or j 0 and Val is 1 then dp(i,j)=1
Else
If Val is 1
Dp=min(dp(i-1,j-1), dp(i-1,j), dp(i,j-1))+1
Ans is Max of ans and dp(i,j)
Return ans*ans

Question 43

Minimum difference subsets.
Given an integer array containing n integers, you need to divide the array into two subsets S1 and S2 such that the absolute diff in their sums is min.
Find and return this minimum possible absolute difference.

Answer 43

First find the sum of all the elements in the array.
Dp(n+1,sum+1)
Dp(i,j) indicates if it is possible to have a subset with sum j using elements upto i
Initially dp table is false
For i 0 it means there are no elements.so irrespective of the value of sum it is not possible to have that value of sum so false
Dp(0,i) is false
For sum value 0 irrespective of how many elements we take, there is always empty set whose sum is 0
So dp(i,0) is True
For all other i,j
We have 2 cases
If the new element Is greater than the sum we are looking for, it will anyway not be included in the set which sums to j. So ans is dp(i-1,j)

Case 2 if it is smaller than sum. Then we have 2 choices of whether to include it in the subset or no
Dp(i,j) =dp(i-1, j-A(i-1)) or dp(i-1,j)

Now we are interested only in the last row of dp table
Ans is int_max
Abs difference will be sum-2j
Traverse and find the min of this value and return

Question 44

Unique paths in a grid with obstacles. From 1,1 to m,n

Answer 44

Dp(m+1, n+1)
For all i and j
 Dp(i,j)=0
 If Val is 1 continue
 If(i or j is zero) dp(i,j)=1
 If i >0
 Dp(i,j)+=dp(i-1,j)
If j> 0
 Dp(i,j)+=dp(i,j-1)

Ret dp(n-1,m-1)

Question 45

Minimum sum path in a triangle

Given a triangle find path sum from top to bottom. Each step you may move to adjecent nodes in the row below

Answer 45

Dp(n,0)
Initially fill dp array with elements from the last row
For i from 0-n 
 Dp[i] = a(n-1,i)
Now starting from the last but one row to the top, in each row for every element we consider paths reaching that element. We have two choices from its two children path. We will chose the child which has lowe value.bthe two children will be present at dp(j) dp(j+1)
 Sum of children paths
For i from n-2 to 0;
 For j from 0 to m
  Dp(i,j)= min(dp(j),dp(j+1))+a(i,j)

Lastly we will converge to dp(0) which has the ans

Question 46

Coin sum infinite
You are given a set of coins s , in how many ways can you make sum assuming you have infinite amount of each coin in the set

Answer 46

Dp(sum+1)
For i from 0 to n
For j = coins(i) j<= sum, j++
Dp(j)=dp(j-coin(i))

Return dp(sum)

Question 47

Maximum product subarray

Find the contiguous subarray within an array which has the longest product. Return maximum product possible

Answer 47

Int ans=a(0)
Int min_arr=A(0)
Int max_arra=a(0)
For i from 1 to n
 If a(i) < 0
  In such a case max product after multiplication will become min product
  Swap min arra and max arra
Max-arr= max(a(i), a(i)*max_arr)
Min_arr=min(a(i), a(i)*min_arr)
Ans=max(ans,max_arr)

Return ans

Question 48

Merge elements
You have to merge a elements of the array into one with minimum possible cost. For any two adj elements of the array x and y, cost is x+y and new value is x+y

Answer 48

Maintain prefix sum array which can be used to obtain the sum of elements between 2 given indices in O(1) time
Dp array with row rep starting index and columns rep ending index. . No need of lower half .
For i=j single element. Cost is 0
Ans at dp(0,n-1)
Use gap method
Dp(i,j) stores the minimum cost of merging array with start index i and end end index j
We can make the first partition of the given set from 1 to n-2
For each such partition the cost will be sum of elements of each partition plus the cost of recursively partioning each partition. We want the min such cost
Dp(i,j) is infi
For k from i to j
Dp(i,j) = min(dp(i,j), prefix(j+1)-prefix(i)+dp(i,k)+dp(k+1,j))

Return dp(0,n-1)

Question 49

Tushar birthday party
Given eating capacity of each friend and filling capacity of dishes , and cost of dishes, find minimum cost to satisfy all friends

Answer 49

We need dp table upto Max capacity. So we need to find max cap of all friends. Dp table will be of length max capacity.
Int n= *max_element(friends.begin(),friends.end())
Dp(0)=0
For a given capacity we can feed dishes whose dish capacity is less. We might need to feed more than one dish.
For different dishes
If (dish_capacity<=i)
We can either feed him this dish or not.
Dp(i)=min(dp(i),cost(j)+dp(i-dish(j))

Then sum the min cost for all friends

Question 50

Equal average partitioning

Given an raay with non negative integers, divide the array into two parts such that they have equal averages

Answer 50

Dp(indices, sum, element) 3d dp array
If element is zero returnsum is 0
 Dp(ind,sum,ele)=false
 If a(ind)<=sum, 
   Then addbit to res
    If (isCheck(ind+1,sum-a(ind), ele-1, a,dp,res)
    Res.pop_back()
If isCheck(ind+1,sum, element,a,dp,res)
 Return dp(ind,sum,ele)=true
Return dp(ind,sum,ele)=false

Main func
Sort the array
 Find sum
Create 3d dp table
For i from 1 to n
 If (sum*i)%n==0
  Then S1 is sum*i 
  S1=S1/n
  If isCheck(0,S1,i,a,t,res)
  Then sort result
   Ans.push_back( res)
   The. Remove these elements from the array
 And add the remaining elements to the ans

Question 51

Word break
Given a string a and a dictionary of word b, determine if a can be segmented into a space seperated sequence of one or more dictionary word

Answer 51

Dict.clear()
Dp.clear()
Dp(n+1,0)
Dp(n)=1
For i from n-1 to 0
 String tmp=""
 For j from i to a.size 
  If dp(i) break
  Temp+=a(j)
  If(dict.find(temp)!=dict end())
 Dp(i)=dp(j+1)

If dp(0) return 1
Else return 0

Question 52

Given a binary tree root, a node x in the tree is named good if in the path from root to x there are no nodes with value greater than x

Answer 52

The idea is to maintain a Maxx variable which stores the Maxx value in the path from root to a node. If the value of the root is greater or equal to Maxx, the it is a good node. So we increment the count by 1 and also update the max
Note that we want the Maxx value to be retained while backtracking.
This is because we want the Maxx values in a particular path from root to node only and not the whole tree
Global variable count
Void good(root, Maxx)
If root-val>=Maxx
Count++
Maxx= root-val
Good(root-left,Maxx)
Good(root-right,Maxx)

Return count

Question 53

Minimum cost climbing stairs
You are given an array of costs. Once you pay the cost for the given step, you can either climb one or two steps.
Find the minimum cost to reach the top stair

Answer 53

Idea: only after paying the cost of a stair can we climb it. So to reach the ith stair we can either reach it from i-1. But even if we come from i-1, we still have to pay the cost for ith step as we want to jump further. If reaching from i-2 also we will have to pay the cost for ith step

Dp(0)=cost(0)
Dp(1)=cost(1)
 Dp(i) =min(dp(i-2), dp(i-1))+cost(i)
Return min dp(n-1),dp(n-2
As for the last step we don't have to pay its cost unless we reached it from i-2

Question 54

Is subsequence

Given 2 strings s and t, find if s is a subsequence if t

Answer 54

Recursion
We maintain two pointers i and j which indicate upto what index we have processed the strings and that they match upto j
If i=m, ret true
If j=n return false
If last char match i++, j++
Else
J++

Similar approach for dp as well.
2d dp array m+1 and n+1
N is for t and m is for s, we need to find if s is subsequence of t
I from 0 to m
J from 0 to n
First row is true

If last char match
 Dp(i,j)=dp(i-1,j-1) or dp(i,  j-1)
Else
Dp(i,j))=dp(i,j-1)
Ret dp(m,n)

Question 55

Maximum units on a truck
Yo are assigned to put some amount of boxes onto one truck.
You are given 2d array boxtype where boxtype(i) (0) is number of boxes of that type and i-1 is value per unit of that type. Return the maximum total number of units that can be put on the truck

Answer 55

Idea is similar to Knapsack with slight modification for the number of elements of each type to consider
trucksize is the capacity
So dp(n+1, trucksize+1)
Dp(i,j) will store the maximum Val which can be obtained by considering upto i elements and with knapsack cap j
For i from 1 to n
For j from 1 to trucksize
Dp(i,j)=0
If number of boxes of type i >j
Dp(i,j)=dp(i-1,j)
Else
For the choice of number of boxes to consider,
For k= 0 to how many ever are there
If k>j break
Dp(i,j)= max(dp(i,j), dp(i-1, j-k)+k*Val)

Return dp(n,trucksize)
But this methods results in tle because of the for loop when the number of boxes is large

Best optimal way is greedy solution

Question 56

Beautiful arrangements
Given an int n, a permutation of 1-n is considered beautiful if for every i, either of the following is true
Perm(i) is divisible by i
And i is divisible by perm(i)

Answer 56

Backtracking. We swap the first element with all possible and for each such swap if the first element is satisfying the condition, then we recursively call on the remaining. We need to swap back to backtrack

Global count
Void func(are,j)
If j=arr size()
 Count++
For i from j to end
 Swap arr(i) and arr(j)
 If conditions satisfy
   Func(arr,j+1)
Swap back

Question 57

Arithmetic slices

Given an integer array, return the number of Arithmetic subarrays.

Answer 57

Dp(n)
Intialize to 0
For i from 2 to end
 If arr(i)-arr(i-1)==arr(i-1)-arr(i-2)
  Dp(i)=dp(i-1)+1
Sum dp array and return sum

Question 58

01 Matrix

Given a binary matrix, return the distance of the nearest 0 for each cell

Answer 58

Observe that dp(i) should ideally be min of its 4 neighbors+1. But if we traverse from top to bottom and left to right, we will only have ans for top and left cells, and not for right and bottom.
Similarly if we traverse from bottom right to top, we will have right and bottom values.
Similarly if we traverse from bottom right to top left, we will have right and bottom values, but not too and left values. But we need all 4 of them

So we divide the problem into 2 parts. First we traverse from top left to bottom right and fill the dp table.
This would give min (left and top)
Now again we traverse from
Bottom right to top left and take the min of dp(i) and right and bottom.
This would give the minimum of all 4 cells
Intialize dp array to infinity

Question 59

Wiggle subsequence

A wiggle sequence is where the difference between successive nuns strictly alternates between positive and negative. Given an array nums, return the length of the longest wiggle subsequence

Answer 59

Idea is similar to lis. We will be considering subsequences ending at i. When at i, we need to consider all js less then i which satisfy the given condition.
But if just maintain a single dp table, how will we know with what sign it is ending? For this we will maintain 2 dp tables
One ending with positive difference and the other ending with negative difference.
If current difference is positive, we need to consider all j which end with negative difference and vice versa.

Dp1 for ending with positive difference.
Dp2 for ending with negative difference
For i from 2 to n
For j from 0 to i
 If nums(i)-nums(j)>0
  Then dp1(i)=max(dp1(i), dp2(j)+1)
Else if negative
 Dp2(i)=max(dp2(i), dp1(j)+1)

Then traverse through the dp table again and store max of dp1(i) and dp2(i)
Then find max Val and return

Question 60

Delete operations of 2 strings

Return minimum number of steps required to make word1 and word2 the same

Answer 60

If last char match
Dp(i,j)= dp(i-1,j-1)
Else
Dp(i,j) =min(dp(i-1,j), dp(i,j-1))+1

Question 61

Count number of teams

Given ratings of n soldiers, you have to form teams of 3 such that their ratings are either increasing or decreasing

Answer 61

We need to maintain 4 vectors
Left smaller
Right greater
Left greater 
Right smaller

The num of inc teams with i as middle element will be
Ls(i)*rg(i)
Sum will be number of increasing teams
Dec teams will be (lg(i)*rs(i))
Sum will give dec teams
Inc sum +dec sum is the total ans

Question 62

Min sum falling path

Answer 62

We would need the minimum of falling paths of first row
The idea is to maintain min sum falling path for every element in the matrix
Last row will be same as matrix
Dp(i,j)= matrix(i,j) + min(dp(i+1,j-1),dp(i+1,j),dp(i+1,j+1))
Do not use min function directly on all three
Use if conditions to check for j crossing boindry

Question 63

Minimum costs for tickets
The days of travel are given as an array. Train tickets are sold in three ways one day pass, 7 day pass and 30 day pass. Their costs are mentioned in cost array. Find min cost to travel all given days

Answer 63

Func(index, arr,costs,dp)
If index>=n return 0
Else you have three options 
One day pass then index will be next index
Cost(0)+func(index+1, arr, costs, dp)
Or 7 day pass 
Then you have to find index of number greater than arr(i)+7
For i from index to n
 If arr(i)>=arr(index+7)
  Then ceil_index=i
Cost(1)+ func(ceil_index, arr,cost,dp)
Similarly for 30 day pass
And return the minimum of the three possible cases

Question 64

Best sight seeing pair

Given values of sights, find max pair such that value(i)+value(j)+i-j is max

Answer 64

Brute force needs two loops
Dp solution using two loops dp(i) stores the best pair with i as first sight
And then we traverse through the dp array and find max and return
But this needs two loops
Can be done in O(n) if we maintain maximum first sight
For int i from 1 to n
Ans=max(ans, Maxx+Val(i)-i)
Maxx=max(Maxx, value(i)+i)
Return ans

Question 65

Out of boundry paths

Answer 65

Dp(i,j,maxmoves) stores the number of paths to boundaries start at i j with at most maxmoves
Memoization
If(out of bounds) ret 1
If moves is 0 return 0
If already cal return it's Val
Else
Ans=0
Ans=ans+func(i+1,j,m,n, maxmoves -1,dp)
Similarly for all 4 neighbors
Return dp(i,j, maxmoves)=ans

Question 66

Longest subarray of 1s after deleting one element

Answer 66

The idea is to maintain left array which stores the max continuous number of 1s including that element
Similarly right array
Then dp(i)=left+right(i)
Dp-=2 iff arr(i)=1
Return max of dp

If left(i-1)==1
Left(i)=left(i-1)+arr(i)
Else
Left(i)=arr(i)

In o(n) tc

Question 67

Count square submatrices with all ones

Given a binary matrix, return how many square submatrices hve all 1s

Answer 67

Dp(i,j) stores the number of square submatrices ending at i,j
To build suares of size 2 we need squares of size 1 and so on
The maximum square size is limited by its 3 neighbor’s
If Val is 1 then
Dp(i,j)= min(dp(i-1,j-1),dp(i,j-1),dp(i-1,j))+1

The sum u all dp values and return it

Question 68

Number of dice rolls with targetsum
Given the number of dice, the number of faces of each dice and targetsum, find the number of ways to roll the dice to sum up to target

Answer 68

Dp(n,target+1)
Dp(i,j) stores the number of ways using i dice and to sum j
First row for j from 1 to faces 1
For i and j
 If i<=j
  Current die can be rolled in faces number of ways
For k from 1 to faces
Dp(i,j)+= dp(i-1,j-k)

Return dp(n-1, target)

Question 69

Minimum cost to cut a stick
Given an integer array cuts where cuts(i) denotes a position you should perform cuts , return the min cost to cut the rod

Answer 69

Dp partion problem
So gap method
Dp(n+1,n+1)
For gap from from 2 to n
For i from 0 to bi+gap<=n
 J=i+gap
 Dp(i,j) = infi
 For k from i+1 to j-1
 Dp(i)=min(dp(i,j), dp(ik)+dp(kj)+j-i
 If dp(i,j) Is infi then make it 0
 Return dp(0,n)

But this will result in tle
Instead we do it on cuts array
Dp(m,m)

Func(i,j, dp, cuts)
If abs(i-j)<=2
 Return 0
If already seen return value
Else
Min_cost=infi
For k from i+1 to j-2
 Int curr_cost=cut(j)-cut(i)+func(i,k,dp,cuts)+func(k,j,dp,cuts)
If min cost

Question 70

Word break

Answer 70

Dp partition problem
Instead of making first cuts at every possible index, we make wise choices and cut only if the current string is a valid word
Dp(n+1,n+1) 1 based index 
For gap from 0 to n
For i from 1 to i+gap<= n
J =i+gap
String temp=s.substr(i-1, gap+1)
If set contains temp then valid
 Dp(i,j)= true
Else 
 Flag =false
 For k from i to j
 If dp(i,k) and dp(k,j)
 Flag = true
 Break
Dp(i,j) = flag

Return dp(1,n)

Question 71

Paint houses 3

Return the minimum cost to paint houses such that there are exactly target nbds

Answer 71

Func(i, prev, t, houses, cost, m,n,target)
If t> target return infi/2
If i>=m if t=target ret 0 else infi/2
If not painted
Then n possibilities. For j same as prev t doesn’t inc, else inc
Ans=min(ans, func (i+1, j+1, j+1==prev?t: t+1, …)
If already painted
Ans=min(ans, func(i+1, houses(i), prev==houses(i)? T:t+1…)
Return ans

Question 72

Delete and earn

Given an array nums you can delete nums(i) and earn nums(i) and you should delete num(i)-1 and nums(i)+1

Answer 72

This is similar to house robber problem
Maximum sum without adjacent elements. Observe that dp(i). Will be max of curr Val*Freq +dp(i-2) or dp(i-1)
 For this we would need all i also it is not space efficient
We need only prev and prev to prev
We can use this
Prev prev=0
Prev=v(0)*m(v(0))
Int curr
For i from 1 to n
Int take = v(i)*m(v(i))
If v(i-1)==v(i)-1
 Then take+=prev prev
Else take+=prev
Int not take=prev
Int curr=max(take and not take)
Prevprev= prev
Prev=curr

Return prev

Question 73

Knight probability on chessboard

Answer 73

Dp_curr (n,n)
Dp_nect(n,n)
Dp_curr(x,y)=1
For moves from 0 to k
For i from 0 to n
 For j from 0 to n
 For all 8 new x y
 If is safe
 Dp_next(newx,newy)=+dp_curr(i,j)/8

Dp_curr=dp_next
Make dp next all 0s

Then traverse through dp current and sum up all the prob and return

Question 74

Champagne towers

Answer 74

Arr(0,0)=poured
For i from to 101
For j from 0 to i
 If (arr(i,j)>1)
  Arr(i+1,j)+=arr(i,j)-1/2
 Arr(i+1,j+1)+=arr(i,j)-1/2
Arr(i,j) =1