时间戳

首页 > 解决方案 > 动态规划：座位安排数量

recursion - 动态规划：座位安排数量

问题描述

这是我最近采访的一家公司提出的问题。前提是，电影院必须遵循距离规则，即每两个坐着的人之间必须有至少六英尺的距离。我们得到一个包含 N 个非负整数的列表，其中 list[k] 是座位 k 和座位 k + 1 之间的距离，单排有 N+1 个座位。我们需要弄清楚有效座位安排的数量。

编辑：经过深思熟虑，这就是我到目前为止所得到的

def count(seats):
    # No seats then no arrangements can be made
    if seats == 0:
        return 0
    elif seats == 1:
        # 1 seat means 2 arrangements -- leave it empty (skip) or occupy it
        return 2
    
    if list[seats-1] < 6:
       return count(seats - 1) + counts(seats - k(seats))
    else:
       return count(seats - 1)

回想一下，该列表将包含座位 i 和座位 i+1 之间的距离，因此在每个座位上，我都会检查当前座位与前一个座位之间的距离是否 >= 6 或 < 6。如果小于 6，那么我可以跳过当前座位，或者我可以占据它。现在这是一个棘手的问题，如果我决定占据座位，我的子问题不是座位 - 1，而是座位 - （跳过的座位数以到达下一个有效座位）。我不确定如何找到这个。另一种情况更简单，前一个座位和当前座位之间的距离> = 6，所以无论我是否占据当前座位，我的子问题，座位数，都会缩小一个。

标签： recursiondynamic-programmingmemoization

解决方案

您可以使用两个指针技术和动态规划来解决这个问题。
这里 dp[i] 代表有效组合的数量，其中第 i 个座位是最后一个使用的座位（最后一个 -> 最大索引）。

代码：

def count(distances):
    pref_dist = answer = 0
    pos = pos_sum = pos_dist = 0
    dp = [1] * (len(distances) + 1)
    for i in range(len(distances)):
        pref_dist += distances[i]
        while(pref_dist - pos_dist >= 6):
            pos_dist += distances[pos]
            pos_sum += dp[pos]
            pos += 1
        dp[i + 1] += pos_sum
    return sum(dp) + 1

时间复杂度：
它是O(n)座位n数（不是O(n^2)），因为在整个代码执行过程中while，大多数情况下条件都为真n（指针pos永远不会减少，每次条件为真时pos加一，pos上限为n）和里面的每个操作它使用恒定的时间。

例子：

  1. 六个座位和距离数组 [5, 2, 4, 1, 2]
    计数（[5, 2, 4, 1, 2]）-> 16
    这些是有效的组合（1 表示采用）：
    000000 101000 000010 100001
    100000 000100 100010 010001 010000
    100100 010010 001001
    001000 010100 000001 101001

  2. 四个座位和距离数组 [8, 10, 16]
    count([8, 10, 6]) -> 16
    每个组合都是有效组合。四个座位 =>2^4组合。

推荐阅读