CODEWITHSUNDEEP
algorithmdynamic-programming
Love Cute Shiba
Love Cute Shiba

Reputation: 101

How to make this DP run in O(NH)?

I have an interesting question puzzling me for a while. It's an exercise in Dynamic Programming in the book "introduction to algorithm".

The telephone company that you are working for has recently taken over the telephone servicesin a new city. You have been assigned specifically to work on the telephone poles on Main street.There are N poles in a row from positions 1 to N, and pole i has height H[i] feet, which is an integer in the range [1,maxH].The city has asked you to make all poles have the same height. For each i, if the i-th pole has height h and the (i−1)-th pole has height h′, then you must pay a tax of C|h−h′|. To help achieve this goal, you can increase the height or decrease the height of any pole to height h with a cost of (H[i]−h)^2. Your task is to decide how to increase or decrease the height of each pole so thatyour company will spend the least amount of money. In particular, you must balance the cost of changing the heights of the poles, with the tax your company will have to pay.

(Hint) you should at least be able do it in O(NH^2), but the best you can do is actually O(HN).

So far I've got O(NH^2). My idea is we will initialize a matrix M with size HxN, each entry M[h,i] represents the minimum cost for first i poles with the i pole height h. My goal is to fill in the whole matrix and examine the last column, namely decide the last pole to which height would be of global minimum cost to our problem.

def DP_pole(H,hmax,C,N):
    initialize empty matrix M[H,N]
    for i from 1 to hmax: #first pole,no tax, only construction fee
        M[i,1] = (H[1] - i)**2
    for n from 2 to n: #column first
        for h from 1 to hmax: #row second
            construction = (H[n]-h)**2 # you pay this construction always
            minimum = min(M[1,n-1]+C|h-1|,......,M[hmax,n-1]+C|h-hmax|)
            M[h,n] = construction + minimum
    
    #------find minimum------#
    
    min = float("-inf")
    for h from 1 to hmax:
        if M[h,N] < min:
            min = M[h,N]
    return min

But he algorithm I got so far cannot be reduced to O(HN) I think (perhaps?). Because the recurrence relation I use is a "Linear" one, to decide each entry of matrix H, I will go search the entire previous column, which takes O(H). There are in total H*N entries in the matrix to be filled in.

Any hints or help would be greatly appreciated. Do I need to come up with a different, more clever recurrence relation?

Upvotes: 3

Views: 561

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59243

You have the right dynamic programming approach, but performing this O(hmax) operation for every h is too expensive:

minimum = min(M[1,n-1]+C|h-1|,......,M[hmax,n-1]+C|h-hmax|)

With a little bit of preprocessing, you can calculate this for each h in constant time.

First, consider the tax on a new pole that is <= the height of the one before it. Let:

upmin[h] = min(M[h,n-1],......,M[hmax,n-1]+C(hmax-h))

This removes the absolute value operation, which lets you calculate the whole array in O(hmax) time, because:

if (h == hmax)
    upmin[h] = M[h,n-1]
else
    upmin[h] = min( M[h,n-1], upmin[h+1]+C )

You can calculate this array in O(hmax) working downward from hmax to 0.

Similarly, we can consider the tax on a pole with height >= the preceding one. Let:

downmin[h] = min(M[1,n-1]+C(h-1),......,M[h,n-1])

You can calculate this array in O(hmax) working upward from 0 to hmax

With those calculations done, for each h, minimum = min(upmin[h],downmin[h]), which of course you can do in constant time.

Upvotes: 3

Related Questions