[Python] Simple DP | Time : O(N) Space : O(N) | First Day Where You Have Been in All the Rooms
Approach\n## Important observations\n We can reach ith room only from (i-1)th room\n Patterns repeat. Hence use DP (Observe the image below)\n\n## Explanation\n
# Approach\n## Important observations\n* We can reach ith room only from (i-1)th room\n* Patterns repeat. Hence use DP (Observe the image below)\n![explanation](https://assets.leetcode.com/users/images/b254581a-adf6-4373-a794-96b399ce1947_1631258725.6442018.png)\n## Explanation\n* We can only move to the (i+1)th room if we visit ith room even number of times\n* So dp[i] = number of days we need to reach (i-1)th and + 1 to move to ith room\n* But when we reach (i-1)th room for the first time it is ODD so we need to go to next[i-1], from which we need to get to (i-1)th room again\n* So dp[i]= dp[i-1] + (dp[i-1]-dp[next[i-1]]+1 )+1\n# Code\n```\nclass Solution:\n    def firstDayBeenInAllRooms(self, nxt: List[int]) -> int:\n        N=len(nxt)\n        dp=[0 for _ in range(N)]\n        mod=10**9+7\n        for i in range(1,N):\n            dp[i]=(dp[i-1]+(dp[i-1]-dp[nxt[i-1]]+1)+1)%mod\n        return dp[-1]\n```\n# Complexity\n# Time\n**O(N)**\n# Space\n**O(N)**\n\nAuthor : [Kiran Puli](https://kiranpuli.github.io/Portfolio/)\nCredits (for image) : [votrubac](https://leetcode.com/votrubac)
['Dynamic Programming', 'Python']