跳房子（字节算法题）

存在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
输入
3
1 2 2

输出
8

思路：动态规划

递推：
dp[i]表示走到第i个房子前经历的步数
dp[1] = 0
dp[2] =2
dp[3] =4
dp[4] = dp[3]+1 +(dp[3]-dp[2])+1

找规律：i从1开始
dp[1] =0
当p[i] == i 时 dp[i] =dp[i-1]+2;
当p[i] != i 时 dp[i] = dp[i-1] +1+(dp[i-1]-dp[p[i-1]])+1=2*dp[i-1] - dp[p[i-1]] +2;

再进行合并：
dp[1] =0
当i>1时： dp[i] =2*dp[i-1] - dp[p[i-1]] +2;

题解（java）

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

测试用例：
70
1 1 2 3 4 3 5 2 2 4 8 6 13 6 13 3 5 4 5 10 11 9 11 8 12 24 21 6 9 29 25 31 17 27 3 17 35 5 21 11 27 14 33 7 33 44 22 33 21 11 38 46 53 46 3 22 5 27 55 22 41 25 56 61 27 28 11 66 68 13

一开始对第一次输出的dp[n+1]为负值不理解，将所有的dp[i]与dp[p[i]]的情况输出：
发现%mod操作后,存在 2dp[i-1]< dp[p[i-1]的情况

dp[1]0  dp[p[1]0
dp[2]2  dp[p[2]0
dp[3]6  dp[p[3]2
dp[4]12  dp[p[4]6
dp[5]20  dp[p[5]12
dp[6]30  dp[p[6]6
dp[7]56  dp[p[7]20
dp[8]94  dp[p[8]2
dp[9]188  dp[p[9]2
dp[10]376  dp[p[10]12
dp[11]742  dp[p[11]94
dp[12]1392  dp[p[12]30
dp[13]2756  dp[p[13]2756
dp[14]2758  dp[p[14]30
dp[15]5488  dp[p[15]2756
dp[16]8222  dp[p[16]6
dp[17]16440  dp[p[17]20
dp[18]32862  dp[p[18]12
dp[19]65714  dp[p[19]20
dp[20]131410  dp[p[20]376
dp[21]262446  dp[p[21]742
dp[22]524152  dp[p[22]188
dp[23]1048118  dp[p[23]742
dp[24]2095496  dp[p[24]94
dp[25]4190900  dp[p[25]1392
dp[26]8380410  dp[p[26]2095496
dp[27]14665326  dp[p[27]262446
dp[28]29068208  dp[p[28]30
dp[29]58136388  dp[p[29]188
dp[30]116272590  dp[p[30]58136388
dp[31]174408794  dp[p[31]4190900
dp[32]344626690  dp[p[32]174408794
dp[33]514844588  dp[p[33]16440
dp[34]29672731  dp[p[34]14665326
dp[35]44680138  dp[p[35]6
dp[36]89360272  dp[p[36]16440
dp[37]178704106  dp[p[37]44680138
dp[38]312728076  dp[p[38]20
dp[39]625456134  dp[p[39]262446
dp[40]250649817  dp[p[40]742
dp[41]501298894  dp[p[41]14665326
dp[42]987932464  dp[p[42]2758
dp[43]975862165  dp[p[43]514844588
dp[44]436879737  dp[p[44]56
dp[45]873759420  dp[p[45]514844588
dp[46]232674247  dp[p[46]436879737
dp[47]28468759  dp[p[47]524152
dp[48]56413368  dp[p[48]514844588
dp[49]-402017850  dp[p[49]262446
dp[50]-804298144  dp[p[50]742
dp[51]-608597021  dp[p[51]312728076
dp[52]-529922109  dp[p[52]232674247
dp[53]-292518456  dp[p[53]-292518456
dp[54]-292518454  dp[p[54]232674247
dp[55]-817711153  dp[p[55]6
dp[56]-635422303  dp[p[56]524152
dp[57]-271368749  dp[p[57]20
dp[58]-542737516  dp[p[58]14665326
dp[59]-100140349  dp[p[59]-817711153
dp[60]617430457  dp[p[60]524152
dp[61]234336757  dp[p[61]501298894
dp[62]-32625378  dp[p[62]4190900
dp[63]-69441654  dp[p[63]-635422303
dp[64]496538997  dp[p[64]234336757
dp[65]758741239  dp[p[65]14665326
dp[66]502817147  dp[p[66]29068208
dp[67]976566088  dp[p[67]742
dp[68]953131429  dp[p[68]502817147
dp[69]403445706  dp[p[69]953131429

java中%运算
-5%3=-5-（-5/3向下取整 *3）=-5-（-3）=-2

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！