Rust | 30ms, Top-down DP+Binary Search
Intuition\n\nRecursively compute the number of possible routes from source to destination by finding all possible next hops from that source.\n\n# Approach\n\nC
# Intuition\n\nRecursively compute the number of possible routes from source to destination by finding all possible next hops from that source.\n\n# Approach\n\nCache the recursion results with dynamic programming. The key is `(src, fuel)`.\n\nFinding possible next hops given the amount of fuel can be achieved faster by sorting city positions beforehand and using binary search on the sorted array. However, this does not improve its worse-case time complexity, which is still $O(n)$.\n\n# Complexity\n\n- Time complexity:\n$$O(n^2 k)$$\n\n- Space complexity:\n$$O(nk)$$\n\n# Code\n```\nconst MOD: usize = 1_000_000_007;\n\npub struct DP {\n    vec: Vec<u32>,\n    dest: usize,\n    max_fuel: u32,\n\n    memo: Vec<Vec<Option<usize>>>,\n}\n\nimpl DP {\n    pub fn new(vec: Vec<u32>, dest: usize, max_fuel: u32) -> Self {\n        let memo = vec![vec![None; max_fuel as usize + 1]; vec.len() + 1];\n\n        Self { vec, dest, max_fuel, memo }\n    }\n}\n\nimpl DP {\n    pub fn solve(&mut self, src: usize, fuel: u32) -> usize {\n        if src > self.vec.len() { return 0; }\n        if fuel > self.max_fuel { return 0; }\n\n        if let Some(ret) = self.memo[src][fuel as usize] {\n            return ret;\n        }\n\n        let ret = self.solve_inner(src, fuel);\n        self.memo[src][fuel as usize] = Some(ret);\n        ret\n    }\n\n\n    // Returns the number of possible routes\n    //   from `src` to `dest` with `fuel` available fuel.\n    // Results are cached in `memo`.\n    fn solve_inner(&mut self, src: usize, fuel: u32) -> usize {\n        let mut ret = 0usize;\n        if src == self.dest { ret += 1; } // at least one way\n        if fuel < 1 { return ret; }\n\n        let cur_pos = self.vec[src];\n\n        // Find the indices of possible next hops\n        let l = self.vec.partition_point(|&v| v + fuel < cur_pos);\n        let r = self.vec.partition_point(|&v| v <= cur_pos + fuel);\n\n        for src_next in (l..r).filter(|&v| v != src) {\n            // fuel_next guaranteed to be non-negative\n            // u32::abs_diff is not in Rust 1.58\n            let fuel_next = if self.vec[src_next] > self.vec[src] {\n                self.vec[src_next] - self.vec[src]\n            } else { self.vec[src] - self.vec[src_next] };\n            let fuel_next = fuel - fuel_next;\n\n            ret += self.solve(src_next, fuel_next);\n            ret %= MOD;\n        }\n\n        ret\n    }\n}\n\nimpl Solution {\n    // Sorts and simplifies input array.\n    fn preproc(\n        vec: Vec<i32>,\n        src: usize, dest: usize,\n        fuel: u32\n    ) -> (Vec<u32>, usize, usize) {\n        let src_val = vec[src].min(vec[dest]) as u32;\n        let dest_val = vec[dest].max(vec[src]) as u32;\n\n        if dest_val - src_val > fuel { return (vec![], 0, 0); }\n\n        let mut vec = vec.into_iter()\n            .map(|v| v as u32)\n            .filter(|&v| v != src_val && v != dest_val)\n            .filter(|&v| dest_val <= v + fuel)\n            .filter(|&v| v <= src_val + fuel)\n            .collect::<Vec<_>>();\n        vec.push(src_val);\n        if src_val != dest_val { vec.push(dest_val); }\n        vec.sort_unstable();\n        \n        let src = vec.binary_search(&src_val).unwrap();\n        let dest = vec.binary_search(&dest_val).unwrap();\n\n        (vec, src, dest)\n    }\n\n    pub fn count_routes(\n        vec: Vec<i32>,\n        src: i32, dest: i32,\n        fuel: i32)\n    -> i32 {\n        let (vec, src, dest) = Self::preproc(\n            vec, src as usize, dest as usize, fuel as u32);\n        if vec.is_empty() { return 0; }\n\n        let mut dp = DP::new(vec, dest, fuel as u32);\n\n        dp.solve(src, fuel as u32) as i32\n    }\n}\n```
['Binary Search', 'Dynamic Programming', 'Rust']