#yyds幹貨盤點# 名企真題專題： 附加題

1.簡述：

描述

存在n+1個房間，每個房間依次為房間1 2 3...i，每個房間都存在一個傳送門，i房間的傳送門可以把人傳送到房間pi(1<=pi<=i),現在路人甲從房間1開始出發(目前房間1即第一次通路)，每次移動他有兩種移動政策：    A. 如果通路過目前房間 i 偶數次，那麼下一次移動到房間i+1；    B. 如果通路過目前房間 i 奇數次，那麼移動到房間pi；現在路人甲想知道移動到房間n+1一共需要多少次移動；

輸入描述：

第一行包括一個數字n(30%資料1<=n<=100，100%資料 1<=n<=1000)，表示房間的數量，接下來一行存在n個數字 pi(1<=pi<=i), pi表示從房間i可以傳送到房間pi。

輸出描述：

輸出一行數字，表示最終移動的次數，最終結果需要對1000000007 (10e9 + 7) 取模。

示例1

輸入：

2
1 2      

輸出：

4      

開始從房間1 隻通路一次是以隻能跳到p1即 房間1， 之後采用政策A跳到房間2，房間2這時通路了一次是以采用政策B跳到房間2，之後采用政策A跳到房間3，是以到達房間3需要 4 步操作。      

/**
 *         {   0                                i=1
 * dp[i] = {   dp[i-1]+2                        i>1,pi[i-1]=i-1
 *         {   dp[i-1]+(dp[i-1]-dp[pi[i-1]])+2  i>1,pi[i-1]<i-1
 */
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //    1-n
        int[] pi = new int[n + 1];
        //    1-(n+1)
        long[] dp = new long[n + 2];
        //    1-n
        for(int i = 1; i <= n; ++i){
            pi[i] = sc.nextInt();
        }
        sc.close();
        long mod = (long)(1e9+7);
        //    2-(n+1)
        for(int i = 2; i <= n + 1; ++i){
            if(pi[i - 1] == i - 1){
                dp[i] = (dp[i - 1] + 2) % mod;
            }else{
                dp[i] = (dp[i - 1] + (dp[i - 1] - dp[pi[i - 1]]) + 2) % mod;
            }
        }
//         System.out.println(Arrays.toString(dp));
        System.out.println(dp[n + 1] < 0 ? dp[n + 1] + mod : dp[n + 1]);
    }
}