Java | DP with a diagram
I drew this diagram to help me visualize this problem.\nIn order to move the point marked as green, we have to visit the its previous element 2 times. \nLet pre
I drew this diagram to help me visualize this problem.\nIn order to move the point marked as green, we have to visit the its previous element 2 times. \nLet `pre[i]` be the first time we enter `i` room, so quickly, we can write down the first half of the relationship:  `pre[i] = pre[i-1] + 1 + ...`\n\nThen we consider how long it takes to get back from a random room we got teleported to back to the previous room before green room. \nBut we actually know this already. It is `pre[i - 1] - pre[nextVisit[i - 1]]` because in order to get to previous room right before the green room, all the past rooms must have been visited even number of times, so we can just treat it as we are here the first time and re-use the same calculation.\n\nThus, we complete the re-occuring relationship as `pre[i] = pre[i - 1] + 1 + pre[i - 1] - pre[nextVisit[i - 1]] + 1`\n\nps. I named it as `pre` because I was more thinking about the concept of prefix sum espeically with `pre[i] = pre[i - 1] + .. ` and `pre[i - 1] - pre[x]`, but apparently it is more like `dp`\n\n![image](https://assets.leetcode.com/users/images/b6b9c62b-38f8-4480-8609-dab85dcb04c5_1649543750.0057323.png)\n\n\n\n```Java\nclass Solution {\n    public int firstDayBeenInAllRooms(int[] A) {\n        int m = (int)1e9 + 7;\n        int[] pre = new int[A.length];\n        for (int i = 1; i < A.length; i++){\n            pre[i] = (pre[i - 1] + 1 + (pre[i - 1] - pre[A[i - 1]] + m) % m + 1) % m;\n        }\n\n        return pre[A.length - 1];\n    }\n}\n```
['Java']