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