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

Every day a Leetcode

题目来源：1997. 访问完所有房间的第一天

解法1：动态规划

状态转移：

代码：

/*
 * @lc app=leetcode.cn id=1997 lang=cpp
 *
 * [1997] 访问完所有房间的第一天
 */

// @lc code=start
class Solution
{
private:
    const int mod = 1e9 + 7;

public:
    int firstDayBeenInAllRooms(vector<int> &nextVisit)
    {
        int n = nextVisit.size();
        // dp[i]: 从 0 号房间出发首次到 i+1 花费的天数
        vector<int> dp(n);
        // 初始化
        dp[0] = 2; // 初始化原地待一天 + 访问下一个房间一天
        // 状态转移
        for (int i = 1; i < n; i++)
        {
            int to = nextVisit[i];
            dp[i] = 2 + dp[i - 1];

            if (to != 0)
            {
                dp[i] = (dp[i] - dp[to - 1] + mod) % mod; // 避免负数
            }
            dp[i] = (dp[i] + dp[i - 1]) % mod;
        }
        return dp[n - 2]; // 题目保证n >= 2
    }
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 nextVisit 的元素个数。

空间复杂度：O(n)，其中 n 是数组 nextVisit 的元素个数。