Tag
【動態(tài)規(guī)劃】【數(shù)組】【2024-03-28】
題目來源
1997. 訪問完所有房間的第一天
解題思路
方法一：動態(tài)規(guī)劃
定義狀態(tài)
定義 f[i] 表示第一次到達(dá)房間 i 的日期編號。
根據(jù)題意，首次（第 1 次）訪問房間 i 時(shí)，因?yàn)?1 是計(jì)數(shù)，所以下一次一定會訪問房間 j = nextVisit[i]。只有訪問次數(shù)達(dá)到偶數(shù)才能訪問右邊的下一個(gè)房間，所以在第一次訪問 i 房間時(shí)，我們一定訪問了偶數(shù)次（2次）i 左邊的房間。
換言之，第一次到達(dá)房間 i 時(shí)，[0, ..., i-1] 房間均被訪問了，所以答案直接返回 f[n-1] 即可。
轉(zhuǎn)移關(guān)系
第一次到達(dá)房間 i 是由第二次到達(dá)房間 i-1 遞推得到的。第一次到達(dá)房間 i-1 的日期編號為 f[i-1]，這時(shí)候需要花費(fèi)一天的時(shí)間回退到房間 nextVisit[i-1] （因?yàn)榉块g i-1 是第一次訪問）。
此時(shí)，房間 nextVisit[i-1] 的訪問次數(shù)為奇數(shù)，我們需要從該房間走（訪問）到房間 i-1，花費(fèi)時(shí)間為 f[i-1] - f[nextVisit[i-1]]。這時(shí)房間 i-1 被訪問了偶數(shù)次，可以直接耗時(shí)一天走到房間 i。于是有轉(zhuǎn)移關(guān)系：
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
初始狀態(tài)為 f[0] = 0，表示第一次訪問房間 0 的日期為 0。
實(shí)現(xiàn)代碼
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];
}
};
復(fù)雜度分析
時(shí)間復(fù)雜度：
O
(
n
)
O(n)
O(n)，
n
n
n 為數(shù)組 nextVisit 的長度。
空間復(fù)雜度： O ( n ) O(n) O(n)。
寫在最后
如果您發(fā)現(xiàn)文章有任何錯(cuò)誤或者對文章有任何疑問，歡迎私信博主或者在評論區(qū)指出 ??????。
如果大家有更優(yōu)的時(shí)間、空間復(fù)雜度的方法，歡迎評論區(qū)交流。文章來源：http://www.zghlxwxcb.cn/news/detail-852933.html
最后，感謝您的閱讀，如果有所收獲的話可以給我點(diǎn)一個(gè) ?? 哦。文章來源地址http://www.zghlxwxcb.cn/news/detail-852933.html
到了這里，關(guān)于【每日一題 | 動態(tài)規(guī)劃】訪問完所有房間的第一天的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[Week 19]每日一題（C++，數(shù)學(xué)，并查集，動態(tài)規(guī)劃）](https://imgs.yssmx.com/Uploads/2024/02/433143-1.png)
