1575. Count All Possible Routes

[zeikar]

Problem link

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

Problem Summary

도시의 위치와 사용할 수 있는 연료가 주어질 때 start에서 finish로 갈 수 있는 경우의 수를 구하는 문제.

Solution

딱 보니 dp 로 간단하게 풀린다.
현재 도시 위치 + 남은 연료로 해서 돌려주면 된다.

Source Code

from functools import lru_cache
from typing import List


class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:

        @lru_cache(None)
        def dfs(current, remains):
            if remains < 0:
                return 0
            ret = 0
            if current == finish:
                ret += 1

            for i in range(len(locations)):
                if i != current:
                    ret += dfs(i, remains - abs(locations[current] - locations[i]))
            return ret % 1000000007

        return dfs(start, fuel)