algorithm - 具有 n 层和 k 部电梯的建筑物中的最小电梯问题

Question

所以问题是：

“给定有k部电梯的建筑物的n层数，其中每部电梯 L _i从 a _i层到 b _i层，（给定 a _i和 b _i）找到从一楼到n楼。”

这个问题必须使用动态规划来解决。唯一的问题是我不知道如何开始。那么有没有人有任何类型的想法如何开始这个。

Answer 1

这个问题与Jumping-Game 问题非常相似；除了我们需要基于(ai, bi) values.

让我们先这样做（为 Jump-game 问题创建输入数组）：

N = 10 ## num of total floors
V = [(1, 5), (2, 8), (4, 10), (9, 10)]

nums = [0 for _ in range(N)] ## array we need to fill up to transform this problem to Jump-Game problem

## nums[i] represents the maximum number of floors it can go from floor-i (starting from floor 0 to floor N-1)

for ab_pair in V:
  a, b = ab_pair
  floor_diff = max(b-a, 0)
  if a >= N or a < 0:
    continue
  nums[a-1] = max(nums[a-1], floor_diff)

现在，我们只需要用上面的方法解决 Jump-game 问题input-array: nums。

也就是说，找到到达顶层所需的最少跳跃次数：

    def jump(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0
        
        numsteps = 0
        nc = -1
        tc = -1
        for i in range(len(nums)-1):
            if i >= nc:
                numsteps += 1
                nc = max(tc, i+nums[i])
            else:
                tc = max(tc, i+nums[i])
            if nc >= len(nums)-1:
                return numsteps
        
        return -1

输出：

## For [(1, 5), (2, 8), (4, 10), (9, 10)]

2