1575. Count All Possible Routes

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

Python

特殊結束條件的DP
條件：
1. Fuel > 0
2. 累加cost作為return

from functools import cache


class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        @cache
        def dfs(curr, remain):
            if remain < 0:
                return 0

            result = 1 if curr == finish else 0

            for next_location in range(len(locations)):
                if curr == next_location:
                    continue

                cost = abs(locations[curr] - locations[next_location])
                result += dfs(next_location, remain-cost)

            return result % (10**9+7)

        return dfs(start, fuel)

Python​

Python