Problem statement

https://leetcode.com/problems/count-all-possible-routes/

Solution

Let dp(last, F) be number of ways to go from start to last location such that we have F fuel when we arrived. Then we can check all possible dp(finish, 0), ..., dp(finish, fuel - 1) and choose the best one.

Complexity

Time complexity O(n^2*fuel), space complexity is O(n*fuel).

Code

class Solution:
    def countRoutes(self, L, start, finish, fuel):
        n, M = len(L), 10**9 + 7
        
        @lru_cache(None)
        def dp(last, F):
            if F > fuel: return 0
            if fuel == F: return last == start
            return sum(dp(i, F + abs(L[i] - L[last])) for i in range(n) if i != last) % M
          
        return (sum(dp(finish, i) for i in range(fuel)) + (start == finish)) % M

Remark

There is also in fact O(n*fuel) complexity solution, if we use the fact that we live on the line: let rdp(j, f) be number of ways to go from start to j with f fuel left, such that the last move was made to the left. Similarly, define ldp(j, f). Then we can write the following equations:

ldp(j, f) = rdp(j + 1, f - d(j, j+1)) + 2*ldp(j + 1, f - d(j, j+1)) rdp(j, f) = ldp(j - 1, f - d(j, j-1)) + 2*rdp(j - 1, f - d(j, j-1)),

where d(j, j+1) is distance between cities j and j + 1 (we need to sort them in advance). Also we need to deal with some border cases.