入场安检

标签: 数组 动态规划

难度: Hard

「力扣挑战赛」 的入场仪式马上就要开始了，由于安保工作的需要，设置了可容纳人数总和为 `M` 的 `N` 个安检室，`capacities[i]` 记录第 `i` 个安检室可容纳人数。安检室拥有两种类型： - 先进先出：在安检室中的所有观众中，最早进入安检室的观众最先离开 - 后进先出：在安检室中的所有观众中，最晚进入安检室的观众最先离开 ![c24754f1a5ff56989340ba5004dc5eda.gif](https://pic.leetcode-cn.com/1628843202-cdFPSt-c24754f1a5ff56989340ba5004dc5eda.gif) 恰好 `M+1` 位入场的观众（编号从 0 开始）需要排队**依次**入场安检， 入场安检的规则如下： - 观众需要先进入编号 `0` 的安检室 - 当观众将进入编号 `i` 的安检室时（`0 <= i < N`)， - 若安检室未到达可容纳人数上限，该观众可直接进入； - 若安检室已到达可容纳人数上限，在该观众进入安检室之前需根据当前安检室类型选择一位观众离开后才能进入； - 当观众离开编号 `i` 的安检室时 （`0 <= i < N-1`)，将进入编号 `i+1` 的安检室接受安检。 若可以任意设定每个安检室的类型，请问有多少种设定安检室类型的方案可以使得编号 `k` 的观众第一个通过最后一个安检室入场。 **注意：** - 观众不可主动离开安检室，只有当安检室容纳人数达到上限，且又有新观众需要进入时，才可根据安检室的类型选择一位观众离开； - 由于方案数可能过大，请将答案对 `1000000007` 取模后返回。 **示例 1：** > 输入：`capacities = [2,2,3], k = 2` > > 输出：`2` > 解释： > 存在两种设定的 `2` 种方案： > - 方案 1：将编号为 `0` 、`1` 的实验室设置为 **后进先出** 的类型，编号为 `2` 的实验室设置为 **先进先出** 的类型； > - 方案 2：将编号为 `0` 、`1` 的实验室设置为 **先进先出** 的类型，编号为 `2` 的实验室设置为 **后进先出** 的类型。 > > 以下是方案 1 的示意图： >![c60e38199a225ad62f13b954872edf9b.gif](https://pic.leetcode-cn.com/1628841618-bFKsnt-c60e38199a225ad62f13b954872edf9b.gif) **示例 2：** > 输入：`capacities = [3,3], k = 3` > > 输出：`0` **示例 3：** > 输入：`capacities = [4,3,2,2], k = 6` > > 输出：`2` **提示:** + `1 <= capacities.length <= 200` + `1 <= capacities[i] <= 200` + `0 <= k <= sum(capacities)`

Submission

运行时间: 704 ms

内存: 16.8 MB

class Solution:
    def securityCheck(self, capacities: List[int], k: int) -> int:
        mod=1000000007
        n=len(capacities)
        dp=[0]*(k+1)
        dp[0]=1
        for cap in capacities:
            c=cap-1
            for i in range(k,-1,-1):
                if i>=c:
                    dp[i]+=dp[i-c]
        return dp[k]%mod

Explain

该题解采用动态规划的方法来解决问题，其中dp[i]表示使用当前可用的安检室，恰好容纳i个人的方式的数量。初始化dp[0]为1，即没有人时恰好有一种方式（即不使用任何安检室）。对于每个安检室的容量cap，使用一个内部循环逆序更新dp数组（从k到0），以避免在更新dp[i]时影响之后需要用到的dp[i-c]的值，其中c为cap-1。这是因为每个安检室都可以被视作可以无限次使用来接纳人（完全背包问题）。对于每个i，如果i大于或等于c，则dp[i]将增加dp[i-c]，表示如果前面的状态能够容纳i-c个人，那么当前状态可以通过再加一个容量为c的安检室来容纳i个人。最后返回dp[k] mod 1000000007，即恰好容纳k个人的方式的数量。

时间复杂度: O(N*k)

空间复杂度: O(k)

class Solution:
    def securityCheck(self, capacities: List[int], k: int) -> int:
        mod = 1000000007  # 用于结果的模数操作
        n = len(capacities)  # 安检室数量
        dp = [0] * (k + 1)  # 动态规划数组，长度为k+1
        dp[0] = 1  # 初始化dp[0]
        for cap in capacities:  # 遍历每个安检室的容量
            c = cap - 1  # 安检室容量减一
            for i in range(k, -1, -1):  # 从k递减到0更新dp
                if i >= c:  # 如果当前人数大于等于c，更新dp[i]
                    dp[i] += dp[i - c]  # 累加方式的数量
        return dp[k] % mod  # 返回恰好容纳k个人的方式的数量模1000000007

Explore

在动态规划中初始化dp[0]为1表示当需要容纳的人数为0时，恰好有一种方法来实现这一条件，即不使用任何安检室。这是边界条件的设定，确保在构建解决方案时，有一个基础的起点。这样的初始化是必要的，因为它允许动态规划算法在后续步骤中累加解决方案数量，从而正确地计算出各种人数配置的可能性。

在动态规划中使用逆序更新dp数组的主要原因是防止重复计算。这种方法通常用于处理完全背包问题。如果我们正序更新dp数组，更新dp[i]时使用到的dp[i-c]已经可能在当前迭代中被更新过，因此会导致某些状态被多次计算，从而使结果不正确。逆序更新则确保当我们更新dp[i]时，所依赖的dp[i-c]仍然是上一轮迭代的结果，未被当前轮次影响。这样可以确保每个状态只计算一次，保持算法的正确性。

使用模数1000000007操作主要是为了防止在计算过程中整数溢出，并保证结果的稳定性。1000000007是一个大质数，适合用作取模操作，以减小计算结果的范围，避免超出整数可表示的范围。此外，模数操作也有助于加快计算速度，因为较小的数字计算通常更快。此外，这种模数操作在编程竞赛和算法设计中常用于保证结果的标准化，避免因环境差异导致的结果不一致。