leetcode：1997. 访问完所有房间的第一天【跳跃dp】

分析

必须偶数次才能前进
所以dp[i]记录第一次去到i
必须是第二次去到i - 1再走一步
所以如果说能去到i，必然前面都走了偶数次
那么我们就要探究dp[i]和dp[i - 1]的关系
i - 1 -> next[i - 1] -> i - 1 -> i
具体分析看注释

ac code

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        MOD = 10 ** 9 + 7
        n = len(nextVisit)
        dp = [0] * n # dp[i]表示第一次去到i的时间
        dp[0] = 0

        # 
        # i - 1 -> next[i - 1] -> i - 1 -> i
        for i in range(1, n):
            # i - 1 -> next[i - 1]
            dp[i] = dp[i - 1] + 1
            # core：到了i - 1，可以知道i - 1前面都是偶数次的
            # 等价于next[i - 1] -> i - 1都没走
            # 再走一次next[i - 1] -> i - 1
            dp[i] += dp[i - 1] - dp[nextVisit[i - 1]]
            # i - 1 -> i
            dp[i] += 1
            dp[i] %= MOD
        
        return dp[-1] % MOD

总结

分奇偶的跳跃
注意next只能回跳
意味着i必须由i - 1来到
然后还有一个就是中间全偶数可以当作从来未跳（状态等价）