Python DP with explanation
I imagined the problem as a graph where we have two edges from each node, one for when the room is visited even number of time and one for when it is visited od
I imagined the problem as a graph where we have two edges from each node, one for when the room is visited even number of time and one for when it is visited odd number of times. The important things to note are:\n1. We want the visits for a particular node to become even in order to go to the next node. \n2. The other thing we notice is that all the nodes before that have even number of visits as they have allowed to visit their next node.\n\nNow, when we first visit a node it obviously has odd number of visits so we need to first visit the node `nextVisit[i]` and come back to the same node to get even number of visits. To prevent recomputing this we define `dp[i]` as the number of days it took to reach node `i` starting from node `0` giving use the relation `dp[i+1] = dp[i] + 1(for going to nextVisit[i]) + (dp[i] - dp[nextVisit[i]])(for coming back to same node) + 1(for going to next node)` the final relation is `dp[i+1] = (2 * dp[i] + 2 - dp[nextVisit[i]]) % mod`.\n```\nclass Solution:\n    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:\n        n = len(nextVisit);\n        dp = [0 for _ in range(n)];\n        mod = int(1e9+7);\n        for i in range(n-1):\n            dp[i+1] = (2 * dp[i] + 2 - dp[nextVisit[i]]) % mod;\n        return dp[n-1];\n```
[]