Derivation of DP Solution
An important observation is that when we are at index i, all j < i must have been visited an even number of times, that is, all positions to the left look as if
An important observation is that when we are at index `i`, all `j < i` must have been visited an even number of times, that is, all positions to the left look as if they have never been visited, this hints at the recursive nature of the problem. Let\'s define `f(i)` to be the number of steps it takes to reach `i+1` from `i`, we have  \n```0\nf(i) == SUM[f(j), j in [next[i], i)] + 2\n```\nTo illustrate this relation, let\'s suppose  `next[5] == 2`, observe how `f(5) == f(2) + f(3) + f(4) + 2`:\n```\nEEEEEOE  \n     ^\nEEOEEOE  1 step\n  ^\nEEEOEOE  f(2) steps\n   ^\nEEEEOOE  f(3) steps\n    ^\nEEEEEEE  f(4) steps\n     ^\nEEEEEEO  1 step\n      ^\n```\n\nWe can rewrite the recurrence in terms of the prefix sum `F(i) := SUM[f(j), j in [1,i)]`, the minimum number of steps to reach index `i`:\n```0\nF(i) == SUM[f(j), j in [1,i)]\n     == SUM[f(j), j in [1, i-1)] + f(i-1)\n\t == F(i-1) + SUM[f(j), j in [next[i-1], i-1)] + 2\n\t == F(i-1) + (SUM[f(j), j in [1, i-1)] - SUM[f(j), j in [1, next[i-1])]) + 2\n\t == F(i-1) + (F(i-1) - F(next[i-1])) + 2\n```\nWriten as code:\n```\nint m = 1000000007;\nclass Solution {\npublic:\n    int firstDayBeenInAllRooms(vector<int>& next) {\n        vector<long> dp (next.size());\n        for (int i = 1; i < next.size(); ++i)\n            dp[i] = (2 * dp[i-1] - dp[next[i-1]] + 2 + m) % m;\n        return dp.back();\n    }\n};\n```
['Dynamic Programming']