Intuitive DP
Intuition\nHow do we reach room i for the first time? We can only reach it from room i - 1, and we should have visited room i - 1 exactly twice.\nTherefore, fir
# Intuition\nHow do we reach room i for the first time? We can only reach it from room i - 1, and we should have visited room i - 1 exactly twice.\nTherefore, first time to reach room i = (first time to reach room i - 1) + (time to come back to room i - 1 from room i - 1) \n\n# Approach\nUse two dp arrays:\n1) first_time_to_reach[i], first time to reach room i\n2) time_to_come_back[i], time to come back to room i from room i\n\nAs mentioned in the intuition part, \n`first_time_to_reach[i] = first_time_to_reach[i - 1] + time_to_come_back[i - 1] + 1`\nthe trailing + 1 accounts for the 1 step to move from room i - 1 to room i\n\nNow, how long does it take to go back to room i starting from room i?\nFirst, you need to go from room i to room `nextVisit[i]`.\nLets call `j = nextVisit[i]` for simplicity.\nWhen you have reached room j from room i, you must have visited room j odd number of times including this visit. This is because you were from room i, where i > j. It means when you were at room i, room j must have been visited even number of times, otherwise you cannot reach any room larger than j.\nNow you are in room j. You must come back to proceed. This takes you `time_to_come_back[j]` steps. When you have come back to room j, you can take one more step to go to room j + 1. \nYou now have visited room j + 1 odd number of times (same reason as above).\nYou need to spend `time_to_come_back[j + 1]` steps to come back and make the visited times even to proceed.\nYou keep doing this until you return to room i.\nTherefore\n`time_to_come_back[i] = 1 + time_to_come_back[nextVisit[i]] + 1 + time_to_come_back[nextVisit[i] + 1] + 1 + ... + time_to_come_back[i - 1] + 1`\nWe can optimize this by using a prefix sum of `time_to_come_back` to avoid the sumation.\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(N)\n\n# Code\n```\nclass Solution {\npublic:\n    int firstDayBeenInAllRooms(vector<int>& nextVisit) {\n        int n = nextVisit.size();\n        long long M = 1000000000 + 7;\n        vector<long long> first_time_to_reach(n, 0);\n        vector<long long> prefix_sum_time_to_come_back(n + 1, 0);\n        prefix_sum_time_to_come_back[1] = 1;\n\n        // first_time_to_reach[i] = first_time_to_reach[i - 1] + time_to_come_back[i - 1] + 1\n        // time_to_come_back[i] = 1 + time_to_come_back[nextVisit[i]] + 1 + time_to_come_back[nextVisit[i] + 1] + 1 + ... + time_to_come_back[i - 1] + 1;\n\n        for(int i = 1; i < n; ++i) {\n            first_time_to_reach[i] = (first_time_to_reach[i - 1] + prefix_sum_time_to_come_back[i] - prefix_sum_time_to_come_back[i - 1] + 1 + M) % M;\n            prefix_sum_time_to_come_back[i + 1] = (prefix_sum_time_to_come_back[i] + 1 + prefix_sum_time_to_come_back[i] - prefix_sum_time_to_come_back[nextVisit[i]] + i - nextVisit[i] + M) % M;\n        }\n        return first_time_to_reach.back();\n    }\n};\n```
['C++']