主題
題目連結：
題目意譯：
現在有 n 個房間你需要去拜訪，其編號為 0 到 n - 1。每天的天數也被編號，其從 0 開始。你一天將會去到並拜訪一個房間。
一開始在第 0 天，你拜訪房間 0。接下來幾天你拜訪房間的順序決定於以下規則以及一個給定的索引值從 0 開始的長度 n 的陣列 nextVisit：
假設某天你拜訪房間 i，
如果你拜訪房間 i 的次數是奇數次（包含本次），則下一天你將會拜訪的房間被 nextVisit[i] 決定，其中 0 ≦ nextVisit[i] ≦ i；
如果你拜訪房間 i 的次數是偶數次（包含本次），則下一天你將會拜訪的房間 (i + 1) 模 n。
回傳你第一次你拜訪過所有房間的天數之編號。可以證明這樣的日子必會來臨。由於答案可能很大，將其模 10 ^ 9 + 7 後回傳。
限制：
n == nextVisit.length
2 ≦ n ≦ 10 ^ 5
0 ≦ nextVisit[i] ≦ i
範例測資：
範例 1：
輸入： nextVisit = [0,0]
輸出： 2
解釋：
- 在第 0 天，你拜訪房間 0。你到過房間 0 的總次數為 1，其為奇數。
下一天你將拜訪房間 nextVisit[0] = 0。
- 在第 1 天，你拜訪房間 0。你到過房間 0 的總次數為 2，其為偶數。
下一天你將拜訪房間 (0 + 1) 模 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 天為你第一次到過所有的房間。
解題思維：
這題可以利用動態規劃（Dynamic Programming）來解。
定義一陣列 D，其中 D[i] 代表著第一次拜訪房間 i 的日子之編號。而因為第 0 天時我們必定會拜訪房間 0，所以 D[0] = 0。
根據題意，我們能第一次拜訪房間 i 的先決條件是前一天我們拜訪了房間 i - 1「第二次」，也就是說 D[i] 跟 2 × D[i - 1] 有著一些關係。
而再根據題意，當我們拜訪一個房間 i - 1 奇數次時，我們將回去拜訪 nextVisit[i - 1] 這個房間（可能是同一個房間）。因此第二次拜訪房間 i - 1 時，第二次與第一次經過的日子數是 D[i - 1] - D[nextVisit[i - 1]] + 1，因為第一次「後」我們會直接拜訪房間 nextVisit[i - 1] 而不是像第一次「前」從房間 0 到房間 nextVisit[i - 1] 再到房間 i - 1。
因此我們便可以知道 D[i] 之值應為
2 × D[i - 1] - D[nextVisit[i - 1]] + 2
所以我們從 D[0] 推到 D[1]、再推到 D[2]……以此類推直到 D[n - 1]。而 D[n - 1] 即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
