问动态规划:递推关系

EN

我想编写一个动态规划算法来解决以下问题；为此，我想定义适当的递归关系。这就是问题的答案:考虑一条长度为K英里的直线道路，我们试图在这条道路上放置电话天线。可用站点的特征是整数x1、x2、。。。，xn，其中xi表示沿着道路的天线的位置，以英里为单位(0≤xi≤K)。此外，放置在位置xi的天线产生r (0≤i≤n)的收入。连续两个天线之间的距离不能小于或等于5公里。如何和在哪里放置天线，以最大限度地增加收入。

这是我所写的重复关系:可变参数是: k:道路的长度:天线的位置xi-x (i +1)> 5

这是为了最大限度地增加要放置的天线数量。因此，设N是要放置的天线数目。然后N依赖于k和xi。首先，如果将第一天线放置在xi位置，则可以在k公里的位置上放置天线。天线将放置在5+ xi位置的旁边，然后它将保持k-5公里长的k-5公里长的西安，可以在上面放置天线。如果我决定不放置位置xi的天线，那么我就可以将它们放置在5+ xi位置。

因此，我的递推关系如下:n (k，i) = max (Nxi，k) + N5 + xi，N (xi，in) &N (xi，in)

是对的吗？谢谢。

这是我的算法(我希望在O(N)中有一个算法)：

Algorithm Antenna(\emph{int K, int xi, int profit)
{
int K: road lenght
int xi: position of antenna i

While{j < k}
{
    xi = j
    if{xi < k}
    {
        return idealPosition
    }
    j = j+5
    return profit
}
}

关于利润，你越有触角，你就越有利润。