Skip to content

Commit b5676de

Browse files
authored
Update Readme.md
1 parent f4b0914 commit b5676de

1 file changed

Lines changed: 1 addition & 1 deletion

File tree

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

Others/1997.First-Day-Where-You-Have-Been-in-All-the-Rooms/Readme.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,6 @@
66

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

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

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

0 commit comments

Comments
 (0)