Dynamic programming O(N) solution
Intuition\n Describe your first thoughts on how to solve this problem. \nWe reach the ith cell after reaching the (i-1)th cell an even number of times (2 is the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe reach the ```i```th cell after reaching the ```(i-1)```th cell an even number of times (2 is the smallest even number).\nAnd when we reach the ith cell an odd number of times (Smallest being 1), we need to go back to ```nextVisit[i]``` to decrease the number of steps. Going back to any cell ```j``` < ```nextVisit[i]``` will not be optimal since you will have to cover the path from ```j``` til ```nextVisit[i]``` again.\nThe time taken to go from ```nextVisit[i]``` -> ```i``` is:\n```Table[i] - Table[nextVisit[i]-1]```\nSo overall time to get to ```Table[i]``` is\n```2*(Table[i-1] + 1) - Table[nextVisit[i]-1]```.\nThis is the recursive equation.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code\n```\nclass Solution:\n    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:\n        n = len(nextVisit)\n        mod = 10**9 + 7\n        Table = [0] * n\n        Table[0] = 2\n        for i in range(1, n-1):\n            # you visit Table[i]\n            Table[i] = 1 + Table[i-1]\n            # you go back to nextVisit\n            # this would have been visited an odd number of times now\n            Table[i] = (2*Table[i] - (Table[nextVisit[i]-1] if nextVisit[i] else 0 )) % mod\n        return Table[n-2]\n```
['Array', 'Dynamic Programming', 'Python3']