C++ | Detailed Explanation | O(n) DP
There two major observation in the problem.\n(i) If the count of visit of ith room is odd we cannot move forward.\n(ii) In order to move forward from i -> i+1 r
There two major observation in the problem.\n(i) If the count of visit of ith room is odd we cannot move forward.\n(ii) In order to move forward from i -> i+1 room all rooms <= i must have an even count of visit\n\nNow let us assume dp[i] is no. of days required to reach i rooms\ndp[0] = 0\n\nWe start from room 1 now we\'ll have basically two condn. dp[i-1] == nextVisit[i-1]\nor dp[i-1] != nextVisit[i-1];\n\n(i) For fist condn. we will always require 2 more days to reach the next day.\nsay you have nextVisit as : [0,1,2]\n\nfor 0 -> 0 days\n    1 -> 2 days\n    2 -> 4 days\n    \n   and so on\n\nso we can say dp[i] = dp[i-1] + 2;\n\n(ii) For second condn. it\'s a path we retrace say we have nextVisit as : [0,1,0]\n\nfor 0 and 1 it\'ll be case(i)\nfor 2 our path so far is 0->0->1->1->2\nnow from 2 we reach 0 and we again retrace that path hence it becomes\n0->0->1->1->2->0->0->1->1->2->3\n\nSo, we can see total days require is 10 and we can generalise this as\n\ndp[i] = dp[i-1] + (dp[i-1] - dp[nextVisit[i-1]]) + 2\n\nWhich means as follows\ndp[i-1] : is the no. of days require to reach i-1 rooms\ndp[i-1] - dp[nextVisit[i-1]] : is the no. of days to reach i-1th room again from nextVisit[i-1]\n2 : is the i-1 to nextVisit[i-1] + i-1 to i in above example it is from 2->0 and 2->3 that is\n    2 extra days will always be required.\n\nIf you like the explaination please upvote.\n\n```\nclass Solution {\npublic:\n    int firstDayBeenInAllRooms(vector<int>& nextVisit) {\n        int n = nextVisit.size();\n        int mod = 1e9 + 7;\n        long long dp[n];\n        dp[0] = 0;\n        \n        for(int i = 1 ; i < n ; i++)\n        {\n            if(dp[i-1] == nextVisit[i-1])\n                dp[i] = dp[i-1] + 2;\n            else\n                dp[i] = (2 + 2*dp[i-1] + mod - dp[nextVisit[i-1]])%mod;\n        }\n        \n        return (int) dp[n-1]%mod;\n    }\n};\n```
['Dynamic Programming', 'C']