本文主要是介绍LeetCode：1997. 访问完所有房间的第一天（DP Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
1997. 访问完所有房间的第一天
题目描述：
实现代码与解析：
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号房间。
请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 109 + 7 取余后的结果。
示例 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 天是你访问完所有房间的第一天。
提示：
n == nextVisit.length2 <= n <= 1050 <= nextVisit[i] <= i
实现代码与解析：
DP
class Solution {public int firstDayBeenInAllRooms(int[] nextVisit) {int mod = 1000000007;int n = nextVisit.length;long[] f = new long[n];f[0] = 0; // 第一次到达idx0是0，当开始读数据回退的时候才算第一天，所以这里是第0天for (int i = 1; i < n; i++) {int t = nextVisit[i - 1];f[i] = (f[i - 1] + 1 + f[i - 1] - f[t] + 1 + mod) % mod;}return (int)f[n - 1];}
}原理思路：
这题，我只能说看着短，但是这题真难想其实，尤其是哪个官解，写的更是让看不懂的更晕了。
这里的dp[i]数组含义，第一次到第i间房间的天数。
所以答案是确定dp[n - 1]。
最主要的是递推式怎么写？
房间只有偶数次访问才能向前走，所以，当到了第 i 间房间，说明前面的房间一定全部已经访问了偶数次，不然到不了这个房间。（为了书写方便，我用 v 代表nextVisit数组）
第一次到达i - 1的房间时，一定会消耗一天回溯到 v[ i - 1] 的房间， 令v[i - 1] 为 t（方便书写），因为 i - 1之前的房间一定被访问了偶数次，所以v回溯到 t 房间一定是对其的奇数次访问，在这一时刻，t之前的房间一定也是偶数次访问，t 到 i - 1之间的房间也是偶数次访问，所以我们可以看作为第一次到达 t 房间的状态，我愿称之为重置（但以不是最初的时间，只是状态一致），所以直接用 f[ t ] 表示第一次到达t房间的天数进行后面的计算。
这时想要第二次到达i - 1这个房间，就需要重新走一遍已经走过的路，用f[ i - 1] - f[ t ] ，即可表示走这段路花费的时间。这时第二次（偶次）到达了i - 1这个房间，再消耗一天，便到了 i 房间。
这就是递推式f[ i ] 的由来。 f[ i ] = f[i - 1] + 1 + f[i - 1] - f[t] + 1；//注意我两个+1对应粗体字
我愿称之为，虽然我每接近你一步，轮回的次数就会变多，但是我任然想不断的靠近你，即使每次回溯我都要再花费更长的时间重复经历一遍又一遍。
小细节：
开long。
取mod后f[ i - 1] 可能 小于 f [ t ] 所以先 + mod 再 % mod，防止负数出现。
这篇关于LeetCode：1997. 访问完所有房间的第一天（DP Java）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
