C++ DP
See my latest update in repo LeetCode\n\n## Solution 1. DP\n\nLet dp[i] be the number of days needed to jump from room 0 to room i. The answer is dp[N - 1].\n\n
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. DP\n\nLet `dp[i]` be the number of days needed to jump from room `0` to room `i`. The answer is `dp[N - 1]`.\n\nFor `dp[i]`, on top of the days needed for reaching room `i-1`, i.e. `dp[i-1]`, we need these extra days to go from room `i-1` to room `i`.\n\n* If `A[i-1] == i-1`, we just need 2 days\n* Otherwise, we need to jump to room `A[i-1]` first, taking 1 day. Then spent `dp[i-1] - dp[A[i-1]]` days to go from room `A[i-1]` to room `i-1` again. Lastly, take 1 day to go from room `i-1` to room `i`. So in total, we need extra `2 + dp[i-1] - dp[A[i-1]]` days.\n\nAfter some simplification, we get the following:\n```\ndp[i] = dp[i-1]                           // days needed to reach room i - 1\n          + 2 + dp[i-1] - dp[A[i-1]]      // days needed to go from room i - 1 to room i\n      = 2 + 2 * dp[i-1] - dp[A[i-1]]\n               where 0 <= i < N - 1\ndp[0] = 0\n```\n\n```cpp\n// OJ: https://leetcode.com/problems/first-day-where-you-have-been-in-all-the-rooms/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(N)\nclass Solution {\npublic:\n    int firstDayBeenInAllRooms(vector<int>& A) {\n        long mod = 1e9 + 7, N = A.size();\n        vector<int> dp(N + 1);\n        for (int i = 1; i < N; ++i) {\n            dp[i] = ((long)2 + 2 * dp[i - 1] - dp[A[i - 1]] + mod) % mod;\n        }\n        return dp[N - 1];\n    }\n};\n```
[]