[Python] DP Explanation O(n)
This is a O(n) DP solution. Main idea here is: for each room, the first visit to i leads to nextVisit[i] on the next day, and the second visit to i leads to i+1
This is a O(n) DP solution. Main idea here is: for each room, the first visit to **i** leads to nextVisit[i] on the next day, and the second visit to **i** leads to **i+1** on the next day. All odd visits can be treated as first visit and all even visits can be treated as second visit. Here\'s an example.\nAssume nextVisit = [0, 0, 0, 0], n = 4. On day 14, all rooms are visited. The visiting log is as the below:\n![image](https://assets.leetcode.com/users/images/7a621866-a768-4113-b3a5-03710657383f_1632103415.5733008.png)\nWe can create 2 DP lists - **firstVisits** and **secondVisits** which stores the day when room **i** is visited first time and second time. The previous example has the following DP values:\n![image](https://assets.leetcode.com/users/images/b20ff8b8-2f89-4e09-9865-378503525497_1632103447.6000285.png)\nNotice:\n* firstVisits[i] = secondVisits[i - 1] + 1\n* secondVisits[i] = firstVisits[i] + 1 when nextVisit[i] == i\n* More generic, secondVisits[i] = secondVisits[i - 1] - firstVisits[nextVisit[i]] + firstVisits[i] + 2, for all possible nextVisit[i]. In the previous example, secondVisits[2] = secondVisits[1] - firstVisits[0] + firstVisits[2] + 2 = 13\n```\nclass Solution:\n    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:\n        modFactor = 10**9 + 7\n        firstVisits = [0]\n        secondVisits = [1]\n        N = len(nextVisit)\n        for i in range(1, N - 1):\n            firstVisits.append((secondVisits[i - 1] + 1) % modFactor)\n            secondVisits.append(\n                (secondVisits[i - 1] - firstVisits[nextVisit[i]] + firstVisits[i] + 2)\n                % modFactor)\n        return (secondVisits[N - 2] + 1) % modFactor\n```
[]