力扣1997-访问完所有房间的第一天

摘要: 方程组辅助 DP 状态设计，简化思路

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，今天我们来看一个比较难想的动态规划问题，容易看出是动态规划，但是状态的设计却很复杂，在同一套阶段划分下，需要两套状态 $f[i]$ 和 $g[i]$ 同时推导，且推导的过程中有互相调用，但又没有后效性。

在 方程组DP 中我们讨论过一个类似的问题，本文的思路类似。

两个转移方程经过代入后，会把另一组状态销掉，最终还是常规的动态规划。但这种类似于方程组 DP 的处理方式可以简化我们设计状态和推导转移方程的思路，更容易出解。

题目

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

你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。

最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：

• 假设某一天，你访问 i 号房间。
• 如果算上本次访问，访问 i 号房间的次数为 奇数 ，那么 第二天 需要访问 nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
• 如果算上本次访问，访问 i 号房间的次数为 偶数 ，那么 第二天 需要访问 (i + 1) mod n 号房间。

请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 1e9 + 7 取余后的结果。

提示：

n == nextVisit.length
2 <= n <= 1e5
0 <= nextVisit[i] <= i

示例 1：
输入：nextVisit = [0,0]
输出：2
解释：

• 第 0 天，你访问房间 0 。访问 0 号房间的总次数为 1 ，次数为奇数。
  下一天你需要访问房间的编号是 nextVisit[0] = 0
• 第 1 天，你访问房间 0 。访问 0 号房间的总次数为 2 ，次数为偶数。
  下一天你需要访问房间的编号是 (0 + 1) mod 2 = 1
• 第 2 天，你访问房间 1 。这是你第一次完成访问所有房间的那天。

示例 2：
输入：nextVisit = [0,0,2]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,0,0,1,2,…] 。
第 6 天是你访问完所有房间的第一天。

示例 3：
输入：nextVisit = [0,1,2,0]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,1,2,2,3,…] 。
第 6 天是你访问完所有房间的第一天。

题解

算法: 动态规划

第 0 天在 0 号房间，假设某一天在 $i$ 号房间，根据给定的行动规则我们发现：

• 如果已访问次数 $i$ 为奇数，则走到 $nextVisit[i]$，也就是原地不动或向后走。
• 如果已访问次数 $i$ 为偶数，则走到 $i + 1$，也就是向前走一步。

由于初始是在 0 号，想要向前走，也就是走到更大编号的房间，只能通过行动规则的第二条先前走一步，不可能向前跳着走。因此第一次访问到 $i$ 号房间时，$0$ 到 $i-1$ 的房间一定都访问过了，并且一定是从 $i-1$ 到达的 $i$。因此当第一次访问到 $n-1$ 时，即访问完所有房间，我们求的就是这一天的日期编号。

一个比较直接的动态规划思路是，考虑定义 $dp[i][s]$ 表示从 $i$ 出发，按照规则走到 $n-1$ 所需的最少步数。其中 $i$ 为阶段，$s$ 为附加信息，取值为 $0, 1$。$s=0$ 表示当前编号访问了偶数次，$s=1$ 表示当前编号访问了奇数次。这样我们所求的实际上就是 $dp[0][1]$。初始化条件只有一个 $dp[n-1][1] = 0$。

但这样定义的问题在于它不满足动态规划中无后效性的要求：原因在于当我们推导后续状态的时候，由于行动规则中有可能会向前走，就会造成回到前面已经完成状态计算的节点的局面。

---

换一种方式考虑，当访问到 $i$ 节点时奇数次的时候，需要根据 nextVisit 不动或往回走，经过若干步再回到 $i$，然后再进入 $i+1$，以此类推。每一次前进道更大的节点都是这种模式。

这样我们定义：

• $f[i]$ 表示起点在 $0$ 且 $0$ 访问次数未奇数次，出发第一次走到 $i$ 所需的步数。
• $g[i]$ 表示从 $i$ 出发，第一步走到 nextVisit[i]，若干步后再回到 $i$ 所经过的步数；

这样我们要求的实际上是 $f[n-1]$。下面考虑状态转移方程：

要第一次走到 $i$，首先要经过 $f[i-1]$ 步第一次走到 $i-1$，然后从 $i-1$ 出发，经过 $g[i-1]$ 步再回到 $i-1$，然后再走一步即可第一次到达 $i$，因此有：

$$f[i] = f[i-1] + g[i-1] + 1$$

当第一次到达 $i$ 时，$i$ 前面的节点一定都到达了偶数次，此时从 $i$ 出发，经过若干步再回到 $i$，如果 nextVisit[i] = i，则 $g[i] = 1$ 即可。否则就要先经过 1 步到达 nextVisit[i]，而此时 nextVisit[i] 的访问次数就变成奇数了，这样经过 $f[i] - f[nextVisit[i]]$ 步，即可回到 $i$，于是有：

$$g[i] = 1 + f[i] - f[nextVisited[i]]$$

初始条件为 $f[0] = 0$，$g[0] = 1$。

代码 (Python)

MOD = int(1e9 + 7)

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        n = len(nextVisit)
        f = [0] * n
        g = [0] * n
        g[0] = 1
        for i in range(1, n):
            f[i] = (f[i - 1] + g[i - 1] + 1) % MOD
            g[i] = (1 + f[i] - f[nextVisit[i]]) % MOD
        return f[n - 1]

---