Dynamic Programming Flashcards
Longest common subsequence
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)
Coin change
Given an array of coin types we need to find out the total possible ways of getting the given sum
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)
Edit distance
Given two strings S1 nd S2, find the minimum number of operations to convert S1 to S2
Insert, del, replace
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))
Longest increasing subsequence
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
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.
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))
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?
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)
Minimum deletions to make an array sorted
N-lis
Maximum sum increasing subsequence
Out of all increasing subsequences we need to find the one with max sum
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
Maximum length of bitonic subsequence
Bitonic sequence is one which first increases and then decreases.
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
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
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
Longest chain of pairs
Given a list of pairs where in each pair a<b></b>
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
Minimum insertions and deletions to convert S1 to S2
Find lcs of S1 and S2 S1 length m S2 length n Lcs l M-l deletions N-l insertions M+n-2l
Shortest common supersequence
Given two strings, we have to find a third string containing the two and is the shortest
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
Longest palindromic subsequence
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
Longest repeating subsequence
Same as lcs but with an additional condition that last char match and their indexes are not the same
Printing lcs
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
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
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)
Min coins to make a value, given infinite supply of every coin type in the set
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>
Egg dropping puzzle
Find the minimum number of egg dropping trials needed to find the threshold floor
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)
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
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)
Maximum sum with no 2 consecutives
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
Number of subsets with given sum
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))
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
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)
Palindrome partitioning
Given a string we have to make minimum cuts in the string so that all parts are palindromic
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)
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
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)
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.
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)
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.
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
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
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)
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
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
Tiling 3A board with 21 dominoes
Find the minimum number of ways to fill the board
An=An-2 +2*(bn-1)
Bn= an-1+ bn-2
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
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)
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.
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)
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?
Dp(i)=dp(i-1)+dp(i-2)
Space optimization by maintaining prev and prev_prev
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.
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)
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
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
Longest Arithmetic Progression
Find longest AP in an integer array of size N and return it’s length
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
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
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)
Best time to buy and sell stocks atmost B times. Find maximum profit you can achieve
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)
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
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
Maximum sum path in BT
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
Kingdom wars
Find the maximum sum submatrix
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
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
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
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.
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
Unique paths in a grid with obstacles. From 1,1 to m,n
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)
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
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
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
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)
Maximum product subarray
Find the contiguous subarray within an array which has the longest product. Return maximum product possible
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
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
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)
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
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
Equal average partitioning
Given an raay with non negative integers, divide the array into two parts such that they have equal averages
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
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
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
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
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
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
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
Is subsequence
Given 2 strings s and t, find if s is a subsequence if t
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)
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
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
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)
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
Arithmetic slices
Given an integer array, return the number of Arithmetic subarrays.
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
01 Matrix
Given a binary matrix, return the distance of the nearest 0 for each cell
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
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
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
Delete operations of 2 strings
Return minimum number of steps required to make word1 and word2 the same
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
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
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
Min sum falling path
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
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
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
Best sight seeing pair
Given values of sights, find max pair such that value(i)+value(j)+i-j is max
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
Out of boundry paths
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
Longest subarray of 1s after deleting one element
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
Count square submatrices with all ones
Given a binary matrix, return how many square submatrices hve all 1s
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
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
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)
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
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
Word break
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)
Paint houses 3
Return the minimum cost to paint houses such that there are exactly target nbds
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
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
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
Knight probability on chessboard
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
Champagne towers
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
