# 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)