附加题

#解析：https://blog.csdn.net/weixin_42001089/article/details/87114410
n = int(input())
home = [int(e)-1 for e in input().split()]
dp = [0 for _ in range(n+1)]
dp[1] = 2
for i in range(2,n+1):
    dp[i] = 2*dp[i-1] - dp[home[i-1]]+2
print(dp[n]%1000000007)

	#include <iostream>



	 



	usingnamespacestd;



	 



	longlongconstm=1000000007;



	intmain()



	{



	    intn;



	    while(cin>>n)



	    {



	        intp[n+1];



	        p[0]=0;



	        for(inti=1; i<=n; i++)



	            cin>>p[i];



	        longlongdp[n+1];



	        for(inti=0; i<=n; i++)



	        {



	            dp[i]=0;



	        }



	        dp[2]=2;



	        for(inti=3; i<=n; i++)



	        {



	            dp[i]=(dp[i-1]+1+dp[i-1]-dp[p[i-1]]+1)%m;



	        }



	        cout << ((dp[n]+1+dp[n]-dp[p[n]]+1)%m+m)%m << endl;



	    }



	}

	//1000000007都是为了避免溢出，实际上是dp[i+1]=dp[i]-dp[pi-1]+2+dp[i]



	#include <iostream>



	usingnamespacestd;



	intmain() {



	    intn;



	    while(cin>>n){



	        intdp[n+1]={0};



	        intpi,tmp;



	        for(inti=0;i<n;i++){



	            cin>>pi;



	            tmp=dp[i]<dp[pi-1]?dp[i]+1000000007:dp[i];



	            dp[i+1]=(2*tmp-dp[pi-1]+2)%1000000007;



	        }



	        cout<<dp[n]%1000000007<<endl;



	    }



	}

'''
上面BPSK大佬有些我自己编的事例通不过，比如 （3 \n 1 2）做了一点修改。
'''
n = int(input())
home = [int(e)-1 for e in input().split()]
dp = [0 for _ in range(n+1)]
dp[1] = 2
id_pi = 0
for i in range(2,n+1):
    if id_pi<len(home)-1:
        if home[id_pi+1]<=i:
            id_pi+=1
    dp[i] = 2*dp[i-1] - dp[home[id_pi]]+2
print(dp[n]%1000000007)

#递归求解，f(i+1)= 2 * f(i) - f(p(i)) + 2 n = int(input())

A = [0] + [int(i) for i in input().split()]

i = 0

B = (len(A)+2)*[0]
cnt = 0


for i in range(3,n+2):
    B[1] = 0
    B[2] = 2
    B[i] = 2*B[i-1] - B[A[i-1]] + 2

print(B[n+1]%1000000007)
    

此题是一个分析规律，总结递推公式的问题。
设首次到达i号位置所需的次数为f(i)。由题设规则容易知道，到达某个点后，若到达次数为奇数，一定会从该点再次返回到该点以前的位置(pi <= i)，那么此后一定会再次到达该点，此时到达次数为偶数，跳转到i + 1，显然到达点i时，点1<=j<i的访问次数均为偶数次。
考虑第1次到达i点，已经使用的步数为f(i),跳转到pi点使用步数1，此时pi点已经访问过的次数为偶数，那么再次到达pi的访问次数为奇数次，则再次重复从pi到i的访问路径，显然这条访问路径的步数为f(i - 1) - f(pi)。然后再次到达i点，此时为第二次到达，转移到i+1，在需要1次。总的步数即为f(i) + (1 + f(i - 1) - f(pi)) + 1 = 2 * f(i) - f(p(i)) + 2。由此递推公式，即可依次计算出i = 1, 2, ..., n, n + 1