Count all possible routes

Array Dynamic Programming Memoization

64.9% acceptance

Feb 25, 2026

1675

You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively. At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish). Return the count of all possible routes from start to finish. Since the answer may be too large, return it modulo 10^9 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_routes(locations: Vec<i32>, start: i32, finish: i32, fuel: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = locations.len();
    let finish = finish as usize;
    // dp[city][fuel] = number of routes from city with fuel remaining to finish
    let mut dp = vec![vec![-1i64; fuel as usize + 1]; n];

    fn solve(
      loc: &Vec<i32>,
      dp: &mut Vec<Vec<i64>>,
      cur: usize,
      finish: usize,
      fuel: usize,
      modv: i64,
    ) -> i64 {
      if dp[cur][fuel] != -1 {
        return dp[cur][fuel];
      }
      let mut ways = if cur == finish { 1 } else { 0 };
      for next in 0..loc.len() {
        if next == cur {
          continue;
        }
        let cost = (loc[cur] - loc[next]).unsigned_abs() as usize;
        if cost <= fuel {
          ways = (ways + solve(loc, dp, next, finish, fuel - cost, modv)) % modv;
        }
      }
      dp[cur][fuel] = ways;
      ways
    }

    solve(
      &locations,
      &mut dp,
      start as usize,
      finish,
      fuel as usize,
      MOD,
    ) as i32
  }
}