[Python] Optimized DP, O(nlogn + n*fuel) beats 100%
Have to admit that DP was not my first solution for this problem, since I couldn\'t figure out a formula for DP below O(n^3 * fuel), so my first solution used a
Have to admit that DP was not my first solution for this problem, since I couldn\'t figure out a formula for DP below O(n^3 * fuel), so my first solution used a priority queue for each location to get O(n^2 * fuel * logn). After digesting other people\'s posts, especially Orthogonal\'s excellent post in C++, I understood the O(n * fuel + sort) DP solution: once locations are sorted, we can focus only on moments in a trip where we reverse directions. The journey is then a series of alternating left/right jumps, except that if we jump over k intermediate locations, we can stop (for free) at any of them, giving us 2^k ways to make this jump. Once we write the recurrence, rewriting the formula for dp_left[j] in terms of dp_left[j+1] and dp_right[j+1] cuts out a factor of n in complexity.\n\nBeyond this, removing unreachable locations at the start and optimizing conditionals in the bottom-up DP loop cuts runtime in half to ~170 ms.\n\n```python\ndef countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n\tMOD = 10 ** 9 + 7\n\tstart_loc = locations[start]\n\tfin_loc = locations[finish]\n\tif abs(start_loc - fin_loc) > fuel:\n\t\treturn 0\n\tlocations.sort()\n\n\tto_remove = []\n\tmin_both, max_both = start_loc, fin_loc\n\tif start_loc > fin_loc:\n\t\tmin_both, max_both = max_both, min_both\n\n\t# Remove unreachable locations: pure unreachable, or impossible to visit and return to finish\n\tfor i, x in enumerate(locations):\n\t\tif x == start_loc or x == fin_loc:\n\t\t\tcontinue\n\t\tif abs(x - start_loc) >= fuel or abs(x - fin_loc) >= fuel:\n\t\t\tto_remove.append(i)\n\t\telif (abs(x-start_loc)+abs(x-fin_loc) > fuel) and (x < min_both or max_both < x):\n\t\t\tto_remove.append(i)\n\tfor j in reversed(to_remove):\n\t\tdel locations[j]\n\n\t# Deal with small input sizes 1-2\n\tn = len(locations)\n\tif n == 1:\n\t\treturn 1\n\tif n == 2:\n\t\tdist_between = locations[1]-locations[0]\n\t\tif start_loc == fin_loc:\n\t\t\treturn 1 + (fuel // (2*dist_between))\n\t\treturn 1 + ((fuel-dist_between) // (2*dist_between))\n\n\tstart_ind = bisect.bisect_left(locations, start_loc)\n\tfinish_ind = bisect.bisect_left(locations, fin_loc)\n\n\tdp_left = [[0] * (fuel+1) for _ in range(n)]\n\tdp_right = [[0] * (fuel+1) for _ in range(n)]\n\n\tans = 1 if start_ind == finish_ind else 0\n\n\t# Add initial step from starting point\n\tif start_ind > 0:\n\t\tif start_loc == locations[start_ind-1]+fuel:\n\t\t\tans += 1\n\t\telse:\n\t\t\tdp_left[start_ind-1][start_loc-locations[start_ind-1]] = 1\n\tif start_ind < n-1:\n\t\tif start_loc == locations[start_ind+1]-fuel:\n\t\t\tans += 1\n\t\telse:\n\t\t\tdp_right[start_ind + 1][locations[start_ind + 1] - start_loc] = 1\n\n\t# Calculate minimum adjacent step size and distances from start\n\tmin_diff = locations[1]-locations[0]\n\tlast = locations[0] - min_diff\n\tmy_dist_from_start = []\n\tfor x in locations:\n\t\tmin_diff = min(min_diff, x-last)\n\t\tlast = x\n\t\tmy_dist_from_start.append(abs(x-start_loc))\n\n\t# Start the DP\n\n\tfor fuel_rem in range(2*min_diff, fuel+1):\n\n\t\t# If we are stepping left\n\t\tfor j in range(0, n - 1):\n\t\t\tif fuel_rem >= my_dist_from_start[j]:\n\t\t\t\tright_diff = locations[j + 1] - locations[j]\n\t\t\t\tif right_diff < fuel_rem:\n\t\t\t\t\tdp_left[j][fuel_rem] = (dp_right[j+1][fuel_rem-right_diff]\n\t\t\t\t\t\t\t\t\t\t\t+ 2*dp_left[j+1][fuel_rem-right_diff]) % MOD\n\n\t\t# If we are stepping right\n\t\tfor j in range(1, n):\n\t\t\tif fuel_rem >= my_dist_from_start[j]:\n\t\t\t\tleft_diff = locations[j] - locations[j-1]\n\t\t\t\tif left_diff < fuel_rem:\n\t\t\t\t\tdp_right[j][fuel_rem] = (dp_left[j-1][fuel_rem-left_diff]\n\t\t\t\t\t\t\t\t\t\t\t + 2*dp_right[j-1][fuel_rem-left_diff]) % MOD\n\n\tans += sum(dp_left[finish_ind]) + sum(dp_right[finish_ind])\n\treturn ans % MOD\n```\nLet me know if you have any questions or if this helped!
['Python']