Data Structure Lecture Note (Week 6, Lecture 17)

Principles for designing DP algorithm

Principle 1:

Only depending on the problem i.e. problem of smaller scale

Optimal subproblem structure (substructure): your combination of subproblems should cover all the cases of the possible optimal solutions for the super-problem; and the optimal solution of the super problem should fall into at least one of the optimal subproblem solutions

Principle 2:

If the algorithm you design needs to choose among all possible optimal solutions of a particular subproblem, then it is very likely it is not going to be a working dynamic programming solution.

Principle 3:

If you fee hard to write recursion, try to add more constraints to your subproblem definitions (make your subproblems smaller). In this case you may make more subproblems.

Maximum continuous sum problem

input: an array A of integers

Output: a continuous subarray of A such that the sum of the numbers are maximized

Subproblem: R[j] = maximum sum up to j’th index, and use j’th number

Again here we use the trick that add additional constarints to the subproblem so that the structure of the recursion is easier

$R[j] = \max {R[j-1]+A[j], A[j] } $

O(N)

Longest Commone Subsequence (LCS)

Given two sequences of letters, try to find the LCS between them

e.g. A = acefddbec

​ B = fceeddbda

ceddb is the LCS

Subsequence doesn’t have to be continuous!

Subproblems:

R(j, k) is the LCS problem of A[0,…,j] and B[0,…,K]

Let’s use R(j,k) to denote the length of maximum LCS from A[0…j] and B[0…k]

what’s the recursion?

dp[i, j] = max( dp[i, j-1], dp[i-1, j], dp[i-1, j-1] + int(A[i] == B[j]) )

Stone Pile Merging Problem

There are N piles of stones in a line, each of weight W[i], you are asked to merge the stone in the following way: you can only merge two neighbor stone pile into a new one, the merging cost is the sum of weight of each pile, the weight of the new pile is the sum of the weight

Ouput: find the best way to merge the piles into one with minimum cost

The greedy algorithm won’t work (it’s hard to prove or disprove! )

Subproblem: dp(j ,k): the minimum cost of merging A[j … k]

$dp(j,k) = \min_{j\le l\le k} { dp(j,l) + dp(l+1, k) + w(j,…,k) } $

Note on implementation:

Perhaps you want the length at the outest loop

for len = 0, ..., N-1
	for j = 0, ..., N-len-1
		k = j+len
		for b = j,...,j+len-1
			dp = min (...)

https://leetcode-cn.com/problems/minimum-cost-to-merge-stones/

Maximum matrix block sum problem

Problem: you are given a matrix with integer numbers, find a block of submatrix such that the sum in that matrix is maximized

It could be done in $O(N^3)$O(N3)!

Naïve algorithm gives $O(N^6)$O(N6)

First improvement:

S[a,b,c,d] sum of the matrix with left upper (a,b) to right bottom (c,d)

S[a,b,c,d] = S[a,b,c-1,d] + ( S[c,0,c,d] - S[c,0,c,b-1] )

For each j, S[j,0,j,x] can be calculated in O(N) time for all x from 1 to N

So this is a O(N^4) algorithm

Any further improvement?

Second Improvement

Let’s have two row indices x and y, for rows between x and y, assume we know the sum C(x,y,j) = S[x,j,y,j]

then we can use O(N) time to find the best block if we force the submatrix has to start from x row and ends in y row.

This is an O(N^3) algorithm

Note, C(x,y,j) can be calculated from C(0,y,j) - C(0,x-1,j) which takes O(N^2) time to fill

Building blocks problems

You are given N wooden blocks, each with a weight Wi and a strength Si for each item i

Please find a way to stack the blocks such that the strength of a block should be larger or equal to the sum of the weights above this block and we want to maximize the number of blocks that are put into the stack

Solution: first sort by S+W.

Now let P[U, K ] be the problem that uses 1 to U items to stack and pick K items, and P[U,K] stores the minimum weight of picking K items.

The best solution is largest K such that P[N, K] has a valid value

P[X, Y] initialized to infinity

P[J, 0] = 0 for any J >= 0