给定一条有路灯的街道，找出点亮整条街道的最低成本

Question

这是一个我正在苦苦挣扎的练习。

一条街有nlamps，第i第lamp在位置我.

最初所有 lamp 都关闭。对于第 i-th lamp 你有 3 个选项：

保持开关状态关闭并且不支付任何费用。
切换到模式1并支付cost1_i。第i-thlamp会点亮位置i.
切换到模式2并支付cost2_i。第i-第lamp会点亮位置i和leftRange_i 左侧更多位置和 rightRange_i 右侧更多位置。例如，如果 i = 5，并且 leftRange_i = 3 并且 _rightRange_i = 2，那么，将灯切换到模式 2 将点亮位置 2、3、4、5、6 和 7

我需要找到点亮所有 lamp 的最低总成本。 cost1、cost2、leftRange和rightRange都是数组.

Answer 1

这是动态规划的基本练习。

我建议您先将数组转换为一组 (interval, cost) 对。然后问问自己：

我可以使用哪个间隔子集以最低成本覆盖整条街道？

将此问题重新表述为对递归更友好的问题，如下所示：

我可以使用哪个区间子集以最低成本覆盖街道 直到索引 i？

这个问题可以这样回答：

在索引 i 之前覆盖街道的最便宜的方法是使用覆盖 i 的灯加上最便宜的覆盖方法街道直到那个灯的左边范围。
- PLUS 部分可以通过查看之前计算的成本来回答，因为该部分严格小于 i
- 用哪个灯来覆盖 i 是通过遍历覆盖 i 的所有灯并选择最便宜的灯来确定的。

当你有了这个递归解决方案后，只需按以下顺序回答问题：

我可以使用哪个间隔子集以最低成本覆盖街道 直到索引 1？ ^{（基本情况）}
我可以使用哪个间隔子集以最低成本覆盖街道 直到索引 2？ ^{（计算涉及查看以前的答案）}
...
我可以使用哪个间隔子集以最低成本覆盖街道 直到索引 n？ ^{（计算涉及查看以前的答案）}

这是第一次尝试：

# Sample data
n = 5
cost1 = [ 10, 20, 10, 5, 3 ]
cost2 = [ 15, 25, 10, 10, 30 ]
leftRange = [ 0, 1, 0, 1, 2 ]
rightRange = [ 2, 0, 1, 1, 0 ]

class LightRange:
    def __init__(self, light, mode, left, right, cost):
        self.light = light
        self.mode = mode
        self.left = left
        self.right = right
        self.cost = cost

    def doesCover(self, i):
        return self.left <= i and i <= self.right


# Transform input data into a set of LightRanges
ranges = []
for i in range(n):
    ranges.append(LightRange(i, 1, i, i, cost1[i]))
    ranges.append(LightRange(i, 2, i - leftRange[i], i + rightRange[i], cost2[i]))


# For convenience: Create an index telling us what ranges covers index i
rangesCoveringI = []
for i in range(n):
    rangesCoveringI.append([])
    for r in ranges:
        if r.doesCover(i):
            rangesCoveringI[i].append(r)


# Declare two variables holding our solution:
# costToCoverI[i] = the lowest cost for lighting up the street from 0 to i
costToCoverI = []
# rangeUsedToCoverI[i] = range used for covering i when lighting up the street from 0 to i
rangeUsedToCoverI = []

# Populate the solution variables going from left to right on the street
for i in range(n):
    # Walk through ranges covering i and determine the cheapest one to use
    bestCostToCoverI = None
    bestRangeToCoverI = None

    for r in rangesCoveringI[i]:
        # Compute cost associated with using this range
        costThisRange = r.cost
        costLeftOfThisRange = 0 if r.left <= 0 else costToCoverI[r.left - 1]
        cost = costThisRange + costLeftOfThisRange

        # Cheapest so far?
        if bestCostToCoverI is None or cost < bestCostToCoverI:
            bestCostToCoverI = cost
            bestRangeToCoverI = r
    
    costToCoverI.append(bestCostToCoverI)
    rangeUsedToCoverI.append(bestRangeToCoverI)

# Final solution: costToCoverI[n - 1] = the lowest cost for lighting up the street from 0 to n
print(f"Total cost: {costToCoverI[n - 1]}")

# Backtrack to figure out final mode selection
i = n - 1
while i > 0:
    r = rangeUsedToCoverI[i]
    print(f"{r.light} set to mode {r.mode}")
    i = r.left - 1

输出：

Total cost: 23
4 set to mode 1
3 set to mode 1
0 set to mode 2

N.B.: 未经测试的代码。

尝试一下，尝试理解每一步。
调试您发现的任何问题。
如果有不明白的地方，请在评论中提出后续问题。

给定一条有路灯的街道，找出点亮整条街道的最低成本

Given a street with lamps, finding minimum cost to light entire street

python

algorithm

dynamic-programming