C++ | DP  | Easy Detailed explanation | Give it a read
Approach\n- Simulating the problem as it is will lead to tle because we will be recalculating the parts when we visit ith room odd number of times and then we g
# Approach\n- Simulating the problem as it is will lead to tle because we will be recalculating the parts when we visit ith room odd number of times and then we go to nextVisit[i] then again come back to i.\n- If we know how much days it will take to go from ith room to nextVisit[i] and then back to ith room (if ith room is visited odd number of times), we can add those days in the final answer and then move forward.\n- Hence for each room we will store the first day when we reached it.\n- This will help us answer our query efficiently because now we can do something like this-\n- For example we are currently at ith room and it is our first visit and it took us 6 days to reach here, now we will go to nextVisit[i] which is say jth room and now as we have stored the first day when we reached jth room, let\'s say it was day 4 so now we can directly answer that it would take (6-4)+1 days to go from ith to jth room and back to ith room.\n- Here we are using dp array to store the first day we visited each room.\n\n\n# Code\n```\nclass Solution {\npublic:\n    int mod = 1e9+7;\n    int firstDayBeenInAllRooms(vector<int>& arr) {\n        long long days = 1;\n        int n = arr.size();\n        vector<int> dp(n,-1);\n        dp[0] = 0;\n        map<int,int> m;\n        m[0] = 1;\n        int i = arr[0];\n        for(;i<n;)\n        {\n            m[i]++;\n            if(m[i]%2!=0)\n            {\n                if(m[i]==1 && dp[i]==-1)\n                dp[i] = days;\n                int nextIdx = arr[i];\n                long long d1 = dp[nextIdx];\n                long long d2 = dp[i];\n                days = (days+(d2-d1)+1+mod)%mod;\n                m[i]++;\n            }\n            if(m[i]%2==0)\n            {\n                i = (i+1)%mod;\n                days = (days+1)%mod;\n                if(i==n-1)\n                break;\n            }\n        }\n        return days;\n    }\n};\n```
['Array', 'Dynamic Programming', 'C++']