---
# System prepended metadata

title: 1997. First Day Where You Have Been in All the Rooms
tags: [Leetcode, Dynamic Programming, Medium]

---

# 1997. First Day Where You Have Been in All the Rooms
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/first-day-where-you-have-been-in-all-the-rooms/description/
## 思路
```dp[i]```表示第一次到第i个room是第几天
第```i```个room只能从第```i-1```个room到达 第一次到达第```i-1```个room的时间是```dp[i-1]``` 到达之后将要去```nextVisit[i-1]``` 那么从```nextVisit[i-1]```再到```i-1```需要```dp[i-1]-dp[nextVisit[i-1]]```天 所以```dp[i] = 2*dp[i-1]-dp[nextVisit[i-1]]+2```
## Code
```python=
class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        n, mod = len(nextVisit), 1e9+7
        dp = [0]*n
        for i in range(1, n):
            dp[i] = int((2*dp[i-1]-dp[nextVisit[i-1]]+2)%mod)
        return dp[-1]
```