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

  |  

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

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


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

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

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

题目

你需要访问 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 取余后的结果。

提示:

1
2
3
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$,因此有:

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

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

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
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]

Share