leetcode 1997.访问完所有房间的第一天

思路：动态规划+前缀和

这道题还是很难的，因为你如果需要推出状态方程是很难想的。

在题中我们其实可以发现，这里在访问nextVisit数组的过程中，其实就是对于当前访问的房子之前的房子进行了回访。

怎么说呢？比如你现在在第i个房间里，你为什么会在第i个房间呢？是因为前面的房间你都已经访问了偶数次才会到达这里的吧？是的，我们发现，在规则上说，其实就是在访问偶数次之后我们才会向右边的房间去，在这之前，也就是这间房子左边，我们都已经访问偶数次了。

那我们不妨可以看看，从某个房间到达奇数次-->这个房间到达偶数次这个状态是怎么样的。我们发现不论你选取哪一个房子，都是要经历这个过程的，所以我们可以把状态方程f的含义定为：

访问第i间房子的奇数次到访问第i间房子的偶数次所需要的天数。这就是f[i]的含义。

那么我们可以推知，从第j间房子访问到第i间房子的总天数就是f[i]=f[j]+f[j+1]+...+f[i-1]+2.

为什么需要+2呢？因为你在第一次访问第i间房子之后，你需要回访，然后再回来的时候才会访问偶数次，也就是访问了2次，也就是两天，其他的那些和，其实就是你回访其他房间所用的时间。

好了，如果我们真需要处理这些和的话，势必会让时间复杂度变成n**2。怎么才能进行优化呢？

说到求和，我们会想到一个知识点，那就是前缀和，前缀和会用On的时间来进行操作，这样的话就好说了，我们就用前缀和进行优化。

设s为前缀和数组，那么s[0]=0，至于为什么需要这样，参考一下灵神在这道题里面的题解的解释：303. 区域和检索 - 数组不可变 - 力扣（LeetCode）

那么，就这样推下去的话：s[1]=f[0],s[2]=f[1]+f[0]......s[i+1]=f[i]+s[i]

而我们上面写的f[i]也就可以化简为：f[i]=s[i]-s[j]+2，我们把这两个式子结合一下，

就变成了：s[i+1]=s[i]*2-s[j]+2。这样就算是完成了

class Solution {
public:int firstDayBeenInAllRooms(vector<int>& nextVisit) {int n=nextVisit.size();const int mod=1e9+7;vector<long>s(n);for(int i=0;i<n-1;i++){int j=nextVisit[i];s[i+1]=(s[i]*2-s[j]+2+mod)%mod;}return s[n-1];}
};