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

LeetCode-1997 访问完所有房间的第一天 #

Solution 1 #

记 $dp[i]$ 代表到 $0$ 号房间需要的天数. 如何到达 $i + 1$ ? 首先, 到达 $i$ 需要 $dp[i]$ 步, 从 $dp[i]$ 到达 $nextVisit[i]$ 需要 $1$ 步, 此时 $nextVisit[i]$ 访问了奇数次，它再到达 $i$ 需要 $dp[i] - dp[j]$ 步, 最后从 $i$ 到 $i + 1$ 需要 $1$ 步, 所以状态转移方程为 $$ dp[i + 1] = 2dp[i] - dp[nextVisit[i]] + 2 $$ 第一次到达 $n - 1$ 房间需要 $dp[n - 1]$ 天.

代码如下:

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