Readme

1997.First-Day-Where-You-Have-Been-in-All-the-Rooms

这道题属于看起来非常难、但想通了非常简单的题。

本题的关键点是要想通：如果你是第一次走到了位置i，那么之前的所有位置（index=0到i-1）你都一定走过了偶数次。这个可以反证。假设你在某个位置j只经过了奇数次，那么根据题意，你必然是会在位置j的左边，不可能前进到位置i。

我们令dp[i]表示第一次走到位置i的时间。根据题意，我们会倒退至位置j = nextVisit[i]. 这时候你一定是第奇数次到达j，之后会经过一段历程然后再次到达位置i。可以想象，这一段历程，与从第一次到达i之后再第一次来到j的历程，是一模一样的：此时除了j是走过了奇数次，其他的位置都是走过了偶数次。所以这段经历需要的时间就是dp[i]-dp[j]。

综上，如果你在dp[i]时刻第一次到达i，那么你就会退回位置j，然后经过dp[i]-dp[j]的时间再次到达位置i，此时你是第二次经过i，就可以再进一步走到i+1. 故递推关系是就是dp[i+1] = dp[i]+1+dp[i]-dp[j]+1.

最终的答案就是dp[n-1].