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 3*A board with 2*1 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 ```