【每日一题 | 动态规划】访问完所有房间的第一天-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题 | 动态规划】访问完所有房间的第一天。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Tag

【动态规划】【数组】【2024-03-28】

题目来源

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

访问完所有房间的第一天,LeetCode每日一题,动态规划,数组,C++,2024-03-28

解题思路

方法一：动态规划

定义状态

定义 f[i] 表示第一次到达房间 i 的日期编号。

根据题意，首次（第 1 次）访问房间 i 时，因为 1 是计数，所以下一次一定会访问房间 j = nextVisit[i]。只有访问次数达到偶数才能访问右边的下一个房间，所以在第一次访问 i 房间时，我们一定访问了偶数次（2次）i 左边的房间。

换言之，第一次到达房间 i 时，[0, ..., i-1] 房间均被访问了，所以答案直接返回 f[n-1] 即可。

转移关系

第一次到达房间 i 是由第二次到达房间 i-1 递推得到的。第一次到达房间 i-1 的日期编号为 f[i-1]，这时候需要花费一天的时间回退到房间 nextVisit[i-1] （因为房间 i-1 是第一次访问）。

此时，房间 nextVisit[i-1] 的访问次数为奇数，我们需要从该房间走（访问）到房间 i-1，花费时间为 f[i-1] - f[nextVisit[i-1]]。这时房间 i-1 被访问了偶数次，可以直接耗时一天走到房间 i。于是有转移关系：

$\\= 2*f[n-1] - f[nextVisit[i-1]] + 2$

base case

初始状态为 f[0] = 0，表示第一次访问房间 0 的日期为 0。

实现代码

class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        int n = nextVisit.size();
        vector<long long> f(n);
        const int MOD = 1e9 + 7;
        for (int i = 1; i < n; ++i) {
            f[i] = (2 * f[i-1] - f[nextVisit[i-1]] + 2 + MOD) % MOD;
        }
        return f[n-1];
    }
};

复杂度分析

时间复杂度： $O (n)$ ， $n$ 为数组 nextVisit 的长度。

空间复杂度： $O (n)$ 。