Python 3 | DP | Explanation
Explanation\n- Fact, when you visit i, then other index less than i have already been visited even number of times. This is due to \n\t- > if you have been in r
### Explanation\n- Fact, when you visit `i`, then other index less than `i` have already been visited even number of times. This is due to \n\t- > if you have been in room i an odd number of times (including the current visit), on the next day you will visit a room with a lower or equal room number specified by `nextVisit[i]` where `0 <= nextVisit[i] <= i`;\n- To reach `i+1`, you need visited `i` for an odd time, then even time + 1; say `dp[i]`: moves need to visited `i`\n\t- odd visit to `i`: `dp[i]`\n\t- back to `nextVisit[i]`: `+1`\n\t- from `nextVisit[i]` to `i`: `dp[i] - dp[nextVisit[i]]`\n\t- odd visit to `i+1`: `+1`\n- Now you have the transition function, see more explanation in below code comments\n### Implementation\n```\nclass Solution:\n    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:\n        n = len(nextVisit)\n        dp = [0] * n\n        mod = int(1e9+7)\n        for i in range(n-1):\n            # dp[i]: moves need to visited `i`\n            # dp[i] - dp[nextVisit[i]] + 1: odd visit at i, then back to nextVisited[i] (+1), then move back to i (dp[i] - dp[nextVisit[i]]) for even visit\n            # dp[i] + 1: even visit at i, then from i to i+1\n            dp[i+1] = (dp[i] - dp[nextVisit[i]] + 1 + dp[i] + 1) % mod\n        return dp[n-1] \n```
['Dynamic Programming', 'Python', 'Python3']