README_EN.md

1575. Count All Possible Routes

中文文档

Description

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]|. Please notice that |x| denotes the absolute value of x.

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 109 + 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
Explanation: It is impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.

 

Constraints:

• 2 <= locations.length <= 100
• 1 <= locations[i] <= 109
• All integers in locations are distinct.
• 0 <= start, finish < locations.length
• 1 <= fuel <= 200

Solutions

Python3

class Solution:
    def countRoutes(
        self, locations: List[int], start: int, finish: int, fuel: int
    ) -> int:
        @cache
        def dfs(i, t):
            if abs(locations[i] - locations[finish]) > t:
                return 0
            res = int(i == finish)
            for j, v in enumerate(locations):
                if j != i:
                    if (cost := abs(locations[i] - v)) <= t:
                        res += dfs(j, t - cost)
            return res % mod

        mod = 10**9 + 7
        return dfs(start, fuel)

Java

class Solution {
    private int[][] f;
    private int[] locations;
    private int target;
    private static final int MOD = (int) 1e9 + 7;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        int n = locations.length;
        f = new int[n + 1][fuel + 1];
        this.locations = locations;
        target = finish;
        for (int i = 0; i < f.length; ++i) {
            Arrays.fill(f[i], -1);
        }
        return dfs(start, fuel);
    }

    private int dfs(int i, int t) {
        if (f[i][t] != -1) {
            return f[i][t];
        }
        if (Math.abs(locations[i] - locations[target]) > t) {
            return 0;
        }
        int res = i == target ? 1 : 0;
        for (int j = 0; j < locations.length; ++j) {
            if (j != i) {
                int cost = Math.abs(locations[i] - locations[j]);
                if (cost <= t) {
                    res += dfs(j, t - cost);
                    res %= MOD;
                }
            }
        }
        f[i][t] = res;
        return res;
    }
}

C++

class Solution {
public:
    const int mod = 1e9 + 7;

    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        int n = locations.size();
        vector<vector<int>> f(n + 1, vector<int>(fuel + 1, -1));
        return dfs(start, fuel, locations, finish, f);
    }

    int dfs(int i, int t, vector<int>& locations, int target, vector<vector<int>>& f) {
        if (f[i][t] != -1) return f[i][t];
        if (abs(locations[i] - locations[target]) > t) return 0;
        int res = i == target;
        for (int j = 0; j < locations.size(); ++j) {
            if (j == i) continue;
            int cost = abs(locations[i] - locations[j]);
            if (cost <= t) res = (res + dfs(j, t - cost, locations, target, f)) % mod;
        }
        f[i][t] = res;
        return res;
    }
};

Go

func countRoutes(locations []int, start int, finish int, fuel int) int {
	n := len(locations)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, fuel+1)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	mod := int(1e9) + 7
	var dfs func(int, int) int
	dfs = func(i, t int) int {
		if f[i][t] != -1 {
			return f[i][t]
		}
		if abs(locations[i]-locations[finish]) > t {
			return 0
		}
		res := 0
		if i == finish {
			res++
		}
		for j, v := range locations {
			if j != i {
				cost := abs(locations[i] - v)
				if cost <= t {
					res = (res + dfs(j, t-cost)) % mod
				}
			}
		}
		f[i][t] = res
		return res
	}
	return dfs(start, fuel)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

...