# 1997. First Day Where You Have Been in All the Rooms

If we use brute force directly, get TLE.

we use 1d dp table, dp[i] means enter number from first day to i day we needed.

So how can we go to get to next room

two case:

First if nums[i] == i, that means we only need two days can go to i+1 room.

`First time this room counter is odd, but we can go back room directly.And Second day we can go to next room.totally 2 days`

Second case, if nums[i] != i, that means we will go to another room(nextVisit[i]) and go back to room(i)

the day we need is dp[i]- dp[nextVisit[i]]

so that if we need to from i to i+1

`dp[i+1] = dp[i] + 2 + dp[i] — dp[nextVisit[i]]`

annsert is dp[N — 1]

code:

`class Solution {public:    int firstDayBeenInAllRooms(vector<int>& nextVisit) {        vector<long> dp(nextVisit.size(), 0);        int mod = 1e9 + 7;        for(int i = 1; i < nextVisit.size();i++){            dp[i] = (dp[i - 1] + 2 + dp[i - 1] - dp[nextVisit[i -1]] + mod) % mod;        }        return dp.back();    }};`

Time Complexity: O(N)

Space Complexity: O(N)