Java | DP, Prefix Sum
The dp recurrence can be further shortened - but it is not a code golf competition.\nSplitting the logic into - 1. calculating the number of days to move to nex
The dp recurrence can be further shortened - but it is not a code golf competition.\nSplitting the logic into - 1. calculating the number of days to move to next room and 2. the prefix sum calculation - made the most sense to me.\nYou can use +/- MOD rather than % for extra performance. \n```\nstatic int MOD= 1_000_000_007;\npublic int firstDayBeenInAllRooms(int[] nextVisit) {\n\tint n= nextVisit.length, ps[]= new int[n];\n\tps[0]= 2;\n\tfor(int i=1; i<n-1; i++){\n\t\tint j= nextVisit[i];\n\t\t// if I arrive to room i with an odd number of visits, how many days will it take me to move to i+1\n\t\tint days= 2 + (ps[i-1]-(j==0 ? 0 : ps[j-1]));\n\t\tif(days<0) days+= MOD;\n\t\tif(days>=MOD) days-= MOD;\n\t\tps[i]= ps[i-1] + days;\n\t\tif(ps[i]>=MOD) ps[i]-= MOD;\n\t}\n\treturn ps[n-2];\n}
[]