C++ DP with explanation
the relationship between dp[i] and dp[i-1]\ndp[i] denotes the first day that I arrive at i, which means i-1 position has been visited twice, once from the begin
1. the relationship between dp[i] and dp[i-1]\ndp[i] denotes the first day that I arrive at i, which means i-1 position has been visited twice, once from the beginning 0, and once from the position nextVisit[i - 1].\nSo dp[i] is composed of three parts:\n* dp[i - 1]: the days from 0 to i-1\n* dp[i - 1] - dp[nextVisits[i-1]] + 1: the days from position nextVisit[i-1] to position i-1\n* 1: from i - 1 to i\nAs a result, dp[i] = dp[i-1] + dp[i-1] - dp[nextVisits[i - 1]] + 1 + 1\n\n2. avoid int overflow\n2 * (1e10 + 7) is nearly INT_MAX, avoid overflow and negative results when calculating dp[i]\n\n```\nclass Solution {\npublic:\n    int firstDayBeenInAllRooms(vector<int>&o nextVisit) {\n        int n = nextVisit.size();\n        int dp[n]; // initialization is not needed\n        dp[0] = 0; // first day \n        for(int i = 1; i < n; ++i){\n            dp[i] = 2 * dp[i - 1] - dp[nextVisit[i - 1]] + 2;\n            if(dp[i] < 0)\n                dp[i] += 1000000007;\n            else dp[i] %= 1000000007;\n        }\n        return dp[n-1];\n    }\n};\n```
[]