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

Question

所以问题是：

"给定 n 层的建筑物有 k 部电梯，其中每部电梯 L_i 从 a_i 层到 b_i 层，（a_i 和 b_i）找到从第一层到第 n 层的最少电梯数量。"

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

Answer 1

这个问题和Jumping-Game problem很相似；除了我们需要根据 (ai, bi) values.

自己创建输入数组

让我们先做（为跳跃游戏问题创建输入数组）：

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)

现在，我们只需要用上面的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

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

Minimal elevator problem in a building with n floors and k lifts

algorithm

dynamic-programming