We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
There was an error while loading. Please reload this page.
1 parent f4b0914 commit b5676deCopy full SHA for b5676de
1 file changed
Others/1997.First-Day-Where-You-Have-Been-in-All-the-Rooms/Readme.md
@@ -6,6 +6,6 @@
6
7
我们令dp[i]表示第一次走到位置i的时间。根据题意,我们会倒退至位置```j = nextVisit[i]```. 这时候你一定是第奇数次到达j,之后会经过一段历程然后再次到达位置i。可以想象,这一段历程,与从第一次到达i之后再第一次来到j的历程,是一模一样的:此时除了j是走过了奇数次,其他的位置都是走过了偶数次。所以这段经历需要的时间就是dp[i]-dp[j]。
8
9
-综上,如果你在dp[i]时刻第一次到达i,那么你就会退回位置j,然后经过dp[i]-dp[j]的时间再次到达位置i,此时你是第二次经过i,就可以再进一步走到i+1. 故递推关系是就是```dp[i+1] = dp[i]+dp[i]-dp[j]+1```.
+综上,如果你在dp[i]时刻第一次到达i,那么你就会退回位置j,然后经过dp[i]-dp[j]的时间再次到达位置i,此时你是第二次经过i,就可以再进一步走到i+1. 故递推关系是就是```dp[i+1] = dp[i]+1+dp[i]-dp[j]+1```.
10
11
最终的答案就是dp[n-1].
0 commit comments