Sponsored
Sponsored
This approach involves using dynamic programming to keep track of the number of ways to reach the target city with the available fuel. We will define a DP table where dp[i][f] represents the number of ways to start from city i with f units of fuel left and reach the target city. We recursively fill this table while considering moves to any other city and subtracting the appropriate fuel cost for that move. The result will be stored in the dp[start][fuel] after exploring all possible routes.
Time Complexity: O(n * fuel * n), where n is the number of cities. This can be reduced using better states or pruning.
Space Complexity: O(n * fuel) for the dp table.
1using System;
2
3class CountRoutes {
4 const int MOD = 1000000007;
5 int[,] dp;
6
7 public int CalculateRoutes(int[] locations, int start, int finish, int fuel) {
8 int n = locations.Length;
9 dp = new int[n, fuel + 1];
10 for (int i = 0; i < n; i++)
11 for (int j = 0; j <= fuel; j++)
12 dp[i, j] = -1;
13 return CountRoutesUtil(locations, start, finish, fuel);
14 }
15
16 private int CountRoutesUtil(int[] locations, int curr, int finish, int fuel) {
17 if (fuel < 0) return 0;
18 if (dp[curr, fuel] != -1) return dp[curr, fuel];
19
20 int result = (curr == finish) ? 1 : 0;
21 for (int i = 0; i < locations.Length; ++i) {
22 if (i != curr) {
23 result = (result + CountRoutesUtil(locations, i, finish, fuel - Math.Abs(locations[i] - locations[curr]))) % MOD;
24 }
25 }
26 return dp[curr, fuel] = result;
27 }
28
29 static void Main() {
30 int[] locations = {2, 3, 6, 8, 4};
31 int start = 1, finish = 3, fuel = 5;
32 CountRoutes obj = new CountRoutes();
33 Console.WriteLine(obj.CalculateRoutes(locations, start, finish, fuel)); // Output: 4
34 }
35}This C# solution offers a class-based implementation for computing routes. It initializes a memoization table and recursively solves each subproblem, caching results with a modulus operation applied to yield final results.
In this approach, a depth-first search (DFS) is implemented to explore possible routes from the start to the finish city. Each travel option is a branch in the DFS tree, where the algorithm explores each choice of stopping at a different city until it no longer has fuel. The recursion keeps track of current fuel and updates the count whenever it reaches the finish city with valid fuel.
Time Complexity: O(n^fuel) without pruning, given recursive branching per city. This complexity is potentially high without memoization.
Space Complexity: O(fuel) due to recursive call stack depth.
class DFSCountRoutes {
const int MOD = 1000000007;
public int CountRoutes(int[] locations, int start, int finish, int fuel) {
return countRoutesDFS(locations, start, finish, fuel);
}
private int countRoutesDFS(int[] locations, int curr, int finish, int fuel) {
if (fuel < 0) return 0;
int result = (curr == finish) ? 1 : 0;
for (int i = 0; i < locations.Length; i++) {
if (i != curr) {
result = (result + countRoutesDFS(locations, i, finish, fuel - Math.Abs(locations[i] - locations[curr]))) % MOD;
}
}
return result;
}
static void Main() {
int[] locations = {2, 3, 6, 8, 4};
DFSCountRoutes obj = new DFSCountRoutes();
Console.WriteLine(obj.CountRoutes(locations, 1, 3, 5)); // Output: 4
}
}The C# solution implements DFS recursively, evaluating new city options as fuel allows. Each branch solution aggregates the result for possible paths, using a modulus for output restraint.