algorithm - 如何让这个 DP 在 O(NH) 中运行？

Question

我有一个有趣的问题困扰了我一段时间。是《算法导论》一书中动态规划的习题。

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

到目前为止，我得到了 O(NH^2)。我的想法是我们将初始化一个大小为 HxN 的矩阵 M，每个条目 M[h,i] 表示第 i 个极点高度为 h 的第 i 个极点的最小成本。我的目标是填充整个矩阵并检查最后一列，即确定最后一个极点的高度对我们的问题具有全局最小成本。

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

但我认为到目前为止我得到的算法不能简化为 O(HN)(也许？)。因为我使用的递归关系是“线性”关系，为了确定矩阵 H 的每个条目，我将搜索整个前一列，这需要 O(H)。矩阵中总共有H*N项需要填写。

任何提示或帮助将不胜感激。我是否需要想出一个不同的、更聪明的递归关系？

Answer 1

你有正确的动态规划方法，但是对每个 h 执行这个 O(hmax) 操作太昂贵了:

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

通过一些预处理，您可以在恒定时间内为每个 h 计算此值。

首先，考虑对高度 <= 前一根杆子的新杆子征税。让:

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

这删除了绝对值运算，这让您可以在 O(hmax) 时间内计算整个数组，因为:

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

您可以在 O(hmax) 中从 hmax 向下计算到 0 来计算此数组。

同样，我们可以考虑对高度 >= 前一根的杆子征税。让:

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

您可以在 O(hmax) 中从 0 向上计算此数组 hmax

完成这些计算后，对于每个 h，minimum = min(upmin[h],downmin[h])，当然你可以在常数时间内完成.