# Count All Possible Routes

This page explains Java solution to problem `Count All Possible Routes` using `Dynamic Programming` algorithm.

## Problem Statement

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 `

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`.

Example 1:

Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
Output: 4
Explanation: The following are all possible routes, each uses 5 units of fuel:
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

Example 2:

Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6
Output: 5
Explanation: The following are all possible routes: 1 -> 0, used fuel = 1
1 -> 2 -> 0, used fuel = 5
1 -> 2 -> 1 -> 0, used fuel = 5
1 -> 0 -> 1 -> 0, used fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5

Example 3:

Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3
Output: 0

Example 4:

Input: locations = [1,2,3], start = 0, finish = 2, fuel = 40
Output: 615088286
Explanation: The total number of possible routes is 2615088300. Taking this number modulo 10^9 + 7 gives us 615088286.

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.Arrays;

class CountAllPossibleRoutes {
private int MOD = (int)1e9 + 7;

public int countRoutes(int[] locations, int start, int finish, int fuel) {
int n = locations.length;
/**
Bottom up Dynamic Programming
dp[i][j]: Number of way you can reach finish from ith position with j quantity of fuel
*/
int[][] dp = new int[n][fuel + 1];

/**
We can reach to finish from finish with even zero quantity of fuel,
so assign 1 for dp[finish][Any quantity of fuel]
*/
Arrays.fill(dp[finish], 1);

for(int startingFuel = 0; startingFuel <= fuel; startingFuel++) {
for(int from = 0; from < n; from++) {
for(int to = 0; to < n; to++) {
if(from == to) continue;
int requiredFuel = Math.abs(locations[from] - locations[to]);
if(startingFuel >= requiredFuel) {
dp[from][startingFuel] = (dp[from][startingFuel] + dp[to][startingFuel - requiredFuel]) % MOD;
}
}
}
}
return dp[start][fuel];
}
}
``````

## Time Complexity

O(N2 * Fuel) Where
N is total number of locations in an input array
Fuel is starting quantity of fuel

## Space Complexity

O(N * Fuel) Where
N is total number of locations in an input array
Fuel is starting quantity of fuel