1997.访问完所有房间的第一天

链接：1997.访问完所有房间的第一天
难度：Medium
标签：数组、动态规划
简介：请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。

题解 1 - python

• 编辑时间：2024-03-28
• 执行用时：289ms
• 内存消耗：39.05MB
• 编程语言：python
• 解法介绍：dp[i][0]表示第i个数,第一次奇数访问的天数，dp[i][1]表示第i个数,第一次偶数访问的天数。

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        n = len(nextVisit)
        dp = [[0, 1] for _ in range(n)]
        mod = 10 ** 9 + 7
        for i in range(1, n):
            dp[i][0] = (dp[i - 1][1] + 1) % mod
            dp[i][1] = (dp[i][0] * 2 + 1 - dp[nextVisit[i]][0]) % mod
        return dp[n - 1][0]