EPI Chapter 17, DP starter

17.1 Combination and permutation. Given an array of weight W[] and target t

1) find the number of combinations of matches which score to t.

2) find the number of permutation sequences of matches which score to t

 

  • C[i, j] = sum(C[i – 1, j – k * W[i]]). Memorization implementation

for(i = [1, W.length]){

for(k = [W[i], target]){

C[k] += C[k – W[i]];

}

}

T = nt , S = t

  • A[j] = sum(j >= W[k] ? 0 : A[j – W[k]]). Key: arrange the last match

T = nt, S = t

 

Variant 17.1.1 Given a score pair <s, s’=””> find the number sequence of matches of two teams t1, t2 such that t1 scores s and t2 score s’.

The same as 17.1 2), arrange the last match

D[s1, s2] = sum(s1 >= W[k] ? 0 : D[s1 – W[k], s2]) + sum(s2 >= W[k] ? 0 : D[s1 , s2 – W[k]])

Variant 17.1.2 Given a score pair <s, s’>, find the maximum number of times the lead team changes.

D[s1, s2] = max(s1 >= W[k] ? 0 : (s1 > s2 && s1 – W[k] < s2 ? [s1 – W[k], s2] + 1 : D[s1 – w[k]]) + max(s2 >= W[k] ? 0 : (s2 > s1 && s2 – W[k] < s1 ? D[s1 , s2 – W[k]] + 1 : D[s1, s2 – W[k]]))

 


 

17.2 Edit Distance

The same as LC edit distance.

D[I, j] = min(1 + min(D[I -1, j], D[I, j – 1]), s1[i] == s2[k] ? D[I – 1][j – 1] : D[I – 1][j – 1] + 1)

 

Variant 17.2.1 Longest subsequence of A and B

L[i][j][k] = A[I + k] == B[j + k] ? L[I][j][k – 1] + 1 : 0

I and j with largest k forms longest subsequence of A and B

 

Variant 17.2.2 Min number of characters to delete to form a palindrome

N[i][j] = A[i] == A[j] ? N[I + 1][j – 1] : min(N[I + 1, j] + 1, N[I, j – 1] + 1, N[I + 1][J – 1] + 2)

 


 

17.3 Combination number c(n, k)

C(n, k ) = c(n – 1, k – 1) + c(n – 1, k)

 

T = nk, S = k

 


 

17.4 Number of ways to go from top left to bottom right

 

Variant 17.4.1 Number of monotone numbers, monotone: D[i] <= D[I + 1]

C[I, k] = sum(C[j, k – 1]); j <= i

C[I, k] is the k-length number with last digit i.

 

Variant 17.4.2 Number of strict monotone numbers

C[I, k] = sum(C[j, k – 1]); j < i

 


 

17.5 Longest sum from top left to bottom right

S[i][j] = max(S[I – 1, j], S[I, j – 1])

 

Variant 17.5.1 if start and end at any point

S[i][j] = max[S[I – 1][j] + A[i][j], S[i][j – 1] + A[i][j], A[i][j]];

 


 

17.6 Word search

The same as LC word search ,with caching for the return value of the same call signature.

 

Variant 17.6.1 The same

Variant 17.6.2 The same

 


 

17.7 0/1 Knapsack

V[I, w] = W[i] <= w ? max(V[I – 1, w], V[I – 1, w – w[i]] + V[i]) : V[I – 1, w]

 

Variant 17.7.1 Knapsack, greedy

 


 

17.8 A jug can only measure water of volume [a, b], but not sure about the exact volume. Use the jugs to measure water of volume [c, d].

 

The logic of last jug.

A[c][d] = OR(A[c – V[k][0]][d – V[k][1]])

 

Variant 17.8.1 A jug can measure water of exact volume in the range [a, b]. Use the jug to measure water of any volume between c and d.

 

The same solution but the border condition is different.

For the original question, L <= j.low && j.high <= H is the border condition for true while the this question has j.low <= L && j.high >= H as border condition for true return value.

 


 

17.9 Ways to tie an election

Find ways to sum to total votes / 2. Use 0/1 knapsack solution here.

 


 

17.10 Divide the stolen items.

Compute whether it is possible to find elements sum to I, I <= total sum / 2. Go through the array and find the min difference.


17.11 maximum subarray sum in a circular array

For none circular array, there exists the famous Kadane’s algorithm.

M[i] = max(M[i – 1] + A[i], A[i]);

The semantics of M[i] is the maximum sum ending at i.

For circular array, three solutions

1) Compute non circular max sum, use the same way to compute the max sum for elements [0, i], [i + 1, end], combine these to get the max sum for circular max. T = n, S = n,

2) Concatenate a copy of the array to the end of the original, use non circular DP, T = n, S = 1

3) Compute the min sum and subtract it from the total sum, min sum is computed using similar way, T = n, S = 1


 

17.12 Word break

Construct the breakable table

S[i, j] = A[i, j] is word || (Exist k, S[i, k] == S[k + 1, j] == true)

DFS

 


17.13 Maximum number of floors can be tested using c cases and d drops

F[c, d] = F[c – 1, d – 1] + F[c, d – 1] + 1

Variant 17.13.1 The same as the solution to the original problem and find the min(d),  F[c, d] > F
Variant 17.13.2 f(N,K) = (f(N-1,K) + K) mod N


 

17.14 Minimum sum from root of a tree to a leaf

S[i, j] = min(S[i – 1, j], S[i – 1, j – 1]) + V[i, j]


17.15 Maximum revenue for the first player to pick coin from two ends

Suppose the opponent will also play with the winning strategy

F[a, b] = max(C[a] + min(F[a + 2, b], F[a + 1, b – 1]), C[b] + min(F[a, b – 2], F[a + 1, b – 1]))

 


17.16 Palindrome decomposition with minimum number of substrings

M[i] = 1 + min(M[j]), S.length >= j >= i && S.substring(i, j) is a palindrome

M is the minimum number of number of substrings for S(i : end)

We need another array is_palindrome to track whether S(i : j) is a palindrome.


17.18 Interleaving string

The same as LC interleaving string.

I[i, j] = S[i] == T[i + j + 1] ? I[i – 1, j] : (T[j] == T[i + j + 1] ? i[i, j – 1] : false)


17.19 Probability of winning a election

The logic of last match. (Think about the last election, what can happen and what does it elicit?

P(r, n) = pn * P(r – 1, n – 1) + (1 – pn) * P(r, n – 1)

P(r, n) is the probability of winning exactly r elections in the first n elections.

Variants: skipped


17.20 Text justification with minimum messiness (cost function)

The cost function is sum(2^ki), ki is the number of trailing spaces for line i.

The logic of last line. (Think about the last line, what can the last line contain and what does it elicit to the total cost)

If the cost function excludes the cost of the last line, first compute the minimum cost as before and then adjust the last line to see what the minimum cost is.

Variant 17.20.1 If the cost function is the total number of spaces, then use a greedy strategy.


17.21 Longest increasing subsequence (LIS)

The classic problem of DP.

1. S[i] = max(j < i && A[j] < A[i] ? S[j] + 1 : 1), T = n2, S = n

2. M[i] is the index of the first element of a subsequence of length i. M[i] is non decreasing and we could now use binary search. T = nlgn, S = n

Variants: skipped


17.22 Minimum power consumed by a tree

L(n) = l(n) + sum(H(c))

H(n) = h(n) + sum(min(H(c), L(c))

L(n) is the minimum power if node n is assigned with a low voltage

 


17.23 The largest rectangle of 1 in a 2D array of boolean values

1 Brute force, T = n3m3 , S = n2m2

2 L[i ,j] and H[i, j] to record the longest stripe of 1 horizontally and vertically ends and starts at A[i, j]. T = n2m, S = nm

3 Maximal rectangle. T = nm, S = m

For square,

1 L[i ,j] and H[i, j] to record the longest stripe of 1 horizontally and vertically ends and starts at A[i, j]. T = nm, S = nm

2 Maximal square.

 

Advertisements

Websites and books for algorithms learning

  • The black book (Chinese)
    • It is the bible of comparative programming. But you need some solid and well built foundation first to have a better reading experience. Otherwise you would drown yourself in endless Google search.
  • 挑战程序设计竞赛(第2版), プログラミングコンテストチャレンジブック (Chinese ,Japanese)
    • Originally written in Japanese, this book has superior explanations of a wide spectrum of algorithms at all levels. Nobody should be disappointed after reading. Download the Japanese version if you like: プログラミングコンテストチャレンジブック
  • Programming Challenges (English, available in almost all major languages)
    • It is written by Skiena, period.
  • The Algorithm Design Manual (English, available in almost all major languages)
    • Again it is written by Skiena, period.
  • Geeks for geeks (English)
    • If you are preparing for Google and Facebook interview, go and get yourself trained. Problems are usually at beginner level.
  • Leetcode, Lintcode
    • For beginners and job hunters.
  • http://www.hankcs.com/ (Chinese)
    • This website is in Chinese and mostly about NLP and algorithms. It is blog like and shows a total learning trail of the blogger who is an amateur expert in NLP. I am totally shocked about his background as an undergrad, starting-from-scratch expert. Having worked in top notch research institute in database/nlp, I have to say my colleagues and even me myself are not really on par with him.
  •  http://blog.csdn.net/cxllyg (Chinese)
    • A blog which has beginner – medium algorithm tutorials. There are tons of Chinese blogs out there like this. I picked this one just as an example.

EPI: Ch18 Greedy and invariants

18.1 word with freq, find the coding scheme with smallest average length?

Hoffman coding: greedy, construct coding tree. Combine two nodes with the lowest frequencies, new combined node is the sum of the freq of two children. Because the code cannot be prefix of any others, the word node must be leafs. The Hoffman coding tree leafs get assigned with code. E.g. left edge -> 0, right edge ->1. Proof easy.

Complexity: T = nlgn, S = n


18.2 Each job has processing time, schedule job such that total waiting time is minimized?

Greedy pick the job with smaller processing time.


18.3 Trapping water

Same as trapping water in LC.

Three ways:

1. Running max, T = n S = n

2. 2 ptrs, T = n S = 1

3. find max, T = n, S = 1

Variant 18.3.1 online algorithm

Go from the first element, store elements in stack

if current element is smaller than running max, clear the stack and update the sum

else go on read the next element

T = n S = n


18.4 n users, each asks for bi storage, m servers. find assignment that minimize the maximal storage required for the servers. Condition: each consecutive two users must be assigned to one server or two consecutive servers.

Solution1: DP L(p, q) = min(max(L(x, q – 1), sum(bi))

Solution2: BS + greedy, search for the upper bound and check


18.5 Implement first fit algorithm for packing.

Tournament tree. Boxes are the leafs and each internal node records the max remaining space for the children boxes.


18.6 3 sum

Variant 18.6.1 distinct 3 sum

Variant 18.6.2 K sum, number of ways of K sum

for(int i = 1; i <= A.length; i ++){
for(int j = 1; j <= k && j <= i; j ++){
for(int t = 1; t <= target; t ++){
ways[i][j][t] = (t >= A[i – 1] ? ways[i – 1][j – 1][t – A[i – 1]] : 0) + ways[i – 1][j][t];
}
}
}

Variant 18.6.3 3 sum code


Gasup problem

The same as LC gas station.

for(int i = 0; i < gas.length; i ++){
costs += cost[i];
gass += gas[i];
if(costs > gass){
start = i + 1;
costs = 0;
gass = 0;
}
}

if(start < gas.length){
return start;
}else{
return -1;
}


18.8 first k number in the form of a + b * sqrt(2)

This is the same as the problem to find the first k numbers which have 3, 5, 7 has factors.

1. Min heap, T = klgk S = k

2. Always insert the smaller element into an array, two ptr, T= k, S = k


18.9 majority element

The same as LC majority element.

Discard two different elements, T = n, S = 1


18.10 2 sum for sorted array on absolute value

1. HashMap, T = n, S = n

2. 2 pointer. find first positive element, last negative element and do normal two pointer sum, T = n, S = 1

Variant 18.10.1

1. HashMap, T = n, S = n

2. 2 pointer. Two pointers start from the beginning of the array (both) and move accordingly. T = nlgn + n, S = 1


18.11 trapping water (|j – i| * min(a[i], a[j]))

Two pointer, move the index with smaller a value, T = n, S = 1.


18.12 find words with frequency of more than ceiling(n / k). Memory should be K and can read for twice.

Discard k different words, HashMap count, get a superset of candidates (at maximum k elements), then read the sequence again to filter out the elements with frequency less than n / k.


 

18.13 longest subarray with sum less or equal to k

1.Brute force, prefix sum, T = n2, S = n

2.Prefix sum, two ptr a and b, find the furthest element c such that prefix[c] – prefix[a] is the smallest, forward ptr b accordingly, T = n, S = n

3. DP, two arr, with/wo, T = n, S = n

Variant 18.13.1

Same as original question.


18.14 max rectangle

This is the same as LC max rectangle. By using a stack T = S = n.

Variant 18.14.1 when there is a largest rectangle, check whether there is a square in there.