字节跳动附加题

题目描述

存在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 步操作。

思路:

一道递推题，dp【i】需要一次奇数和偶数移动，偶数移动 = dp【i-1】+1,奇数移动是dp【i】= dp【i-1】-dp【jump【i-1】】+1。

代码:

package main
import "fmt"
func main(){
    var n int
    fmt.Scan(&n)
    count := make([]int,n+2)
    jump := make([]int,n+1)
    mod := 1000000007
    for i:=1;i<=n;i++{
        fmt.Scan(&jump[i])
    }
    for i:=2;i<=n+1;i++{
        count[i] = (2*count[i-1]%mod-count[jump[i-1]]+2)%mod
    }
    fmt.Println(count[n+1])
}

代码效率：

执行用时：2 ms, 在所有 Go 提交中击败了100.00%的用户
占用内存：988KB, 超过13.64%用Go提交的代码