题解 | #附加题# 动态规划

一开始理所当然地用模拟的方法做，但是怎么都是时间超时，才仔细考虑了一下应该用动态规划

定义为第一次到达第号房间所用的步数

由题意知，若要到达第号房间，则必须到达第号至少两次：

第一次到达号时，再走步则跳回到前面的某个房间，记为，

此时必须重新返回第号房间，那么所花费的步数即为：

，

即

综上，，

最后的是第二次到达号房时再走一步才到

也可以合并同类项：

由于题目提示了要取余1000000007，因此需要特殊处理

#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<long long> tp(n + 1);
        int room;
        for (int i = 1 ; i <= n; i++) {
            cin >> room;
            tp[i] = room;
        }
        vector<long long> dp(n + 2, 0);
        for (int i = 2; i <= n + 1; i++) {
            dp[i] = (dp[i - 1] + 1 + dp[i - 1] - dp[tp[i - 1]] + 1 + MOD) % MOD;
        }
        cout << dp[n + 1] << endl;
    }
    return 0;
}

时间复杂度：O(n)，用于遍历数组

空间复杂度：O(n)，用于存储数组