dp ^^
dp/running sum\ntime: O(N); space: O(N)\n\n\n\n\nint firstDayBeenInAllRooms(vector<int>& n)\n{\n\tint dp[100001]{};\n\tfor(int i{}; i<size(n); ++i)\n\t\tdp[i+1]
**dp/running sum**\n**time: `O(N)`; space: `O(N)`**\n\n![image](https://assets.leetcode.com/users/images/29da1ca5-128a-4f72-82b7-71f60cc97e64_1692049088.2139049.png)\n\n```\nint firstDayBeenInAllRooms(vector<int>& n)\n{\n\tint dp[100001]{};\n\tfor(int i{}; i<size(n); ++i)\n\t\tdp[i+1] = (2*(dp[i]+1)-dp[n[i]]+1000000007ll)%1000000007;\n\treturn dp[size(n)-1];\n}\n```\n\n**Things I understood while working on this problem (not necessarily in the chronological order)**\n\n* second rule prevents infinite "dead" loops;\n* you can\'t immediately go forward if you have visited the point for the first time;\n* you can go forward only if you\'ve done a full loop: `i -> ... -> i`;\n* the problem is inherently recursive: you have to redo what you\'ve already done before.\n* thus simulation may lead to exponentially growing paths. That\'s why we need to reuse previous results in order to avoid that and \'add changes\'.\n* we don\'t need the exact path, we need the number of steps in the path;\n* there are only only three elementary operations: `make one step forward`,  `revert to i-x`, `repeat i-th path`.\n* to get to `i` you need to get to `i-1` that implies iterative solution. \n* the solutions involves operations: `+1`, `reuse previous results`. We can reuse previos results via one of 2 dp methods:\n> - bottom to up iteration with memorisation of the previous results;\n> - up to bottom recursion;\n* the answer is essentially the running sum of `loop(i)+one_step_forward`. Running sum enables queries: what\'s the minimum number operations to get from `i` to `j`.\n\n![image](https://assets.leetcode.com/users/images/cdcc9230-dc67-4068-ba90-245fb8fdaaaa_1692034618.0753334.png)\n\n\n
['C', 'C++']