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)