Tag
【动态规划】【数组】【2024-03-28】
题目来源
1997. 访问完所有房间的第一天
![访问完所有房间的第一天,LeetCode每日一题,动态规划,数组,C++,2024-03-28](https://imgs.yssmx.com/Uploads/2024/04/852933-1.png)
解题思路
方法一:动态规划
定义状态
定义 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
。于是有转移关系:
f [ i ] = f [ i − 1 ] + 1 + f [ i − 1 ] − f [ n e x t V i s i t [ i − 1 ] ] + 1 = 2 ∗ f [ n − 1 ] − f [ n e x t V i s i t [ i − 1 ] ] + 2 f[i] = f[i-1] + 1 + f[i-1] - f[nextVisit[i-1]] + 1 \\= 2*f[n-1] - f[nextVisit[i-1]] + 2 f[i]=f[i−1]+1+f[i−1]−f[nextVisit[i−1]]+1=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
)
O(n)
O(n),
n
n
n 为数组 nextVisit
的长度。
空间复杂度: O ( n ) O(n) O(n)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。文章来源:https://www.toymoban.com/news/detail-852933.html
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。文章来源地址https://www.toymoban.com/news/detail-852933.html
到了这里,关于【每日一题 | 动态规划】访问完所有房间的第一天的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!