huang983

def findCheapestPrice6(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
    """
        Dijkstra
    """
    graph = defaultdict(list)
    for flight in flights:
        graph[flight[0]].append((flight[2], 0, flight[1]))

    minHeap = [nei for nei in graph[src]]
    heapq.heapify(minHeap)

huang983

def findCheapestPrice5(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
    """
        Bellman-Ford
    """
    dp = [float('inf') for _ in range(n)]
    dp[src] = 0
    for _ in range(K + 1):
        dpTmp = dp[:]  # copy by value
        for u, v, cost in flights:
            dpTmp[v] = min(dpTmp[v], dp[u] + cost)  # relax

huang983

def findCheapestPrice4(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
    """
        DP
    """
    dp = [[float('inf') for _ in range(n)] for _ in range(K + 2)]
    dp[0][src] = 0
    for k in range(1, K + 2):
        dp[k][src] = 0
        for u, v, cost in flights:
            dp[k][v] = min(dp[k][v], dp[k - 1][u] + cost) # relax

huang983

def findCheapestPrice3(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        """
            BFS
        """
        graph = defaultdict(list)
        for flight in flights:
            graph[flight[0]].append(flight[1:])

        q = Queue()
        for nei in graph[src]:

huang983

def findCheapestPrice2(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
    """
        DFS w memoization
    """
    cache = {}
    def helper(stop: int, numOfStops: int) -> Union[float, int]:
        if numOfStops > K:
            return float('inf')
        elif stop == dst:
            return 0

huang983

def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
    """
        DFS (TLE)
    """
    def helper(stop: int, numOfStops: int) -> Union[float, int]:
        if numOfStops > K:
            return float('inf')
        elif stop == dst:
            return 0

huang983

def coinChange2(coins: List[int], amount: int) -> int:
    dp = [1] + [0] * amount

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

huang983

from typing import List


def coinChange(coins: List[int], amount: int) -> int:
    def helper(total: int, start: int) -> int:
        if total > amount:
            return 0
        elif total == amount:
            return 1

huang983

def minCostToJump3(x: int, stones: List[int]) -> int:
    dp = [float('inf')] * len(stones)
    dp[0] = stones[0]

    for i in range(1, len(stones)):
        for j in range(1, x + 1):
            if i - j < 0:
                continue
            dp[i] = min(dp[i], stones[i] + dp[i - j])

huang983

def minCostToJump3(x: int, stones: List[int]) -> int:
    dp = [float('inf')] * len(stones)
    dp[0] = stones[0]

    for i in range(1, len(stones)):
        for j in range(1, x + 1):
            if i - j < 0:
                continue
            dp[i] = min(dp[i], stones[i] + dp[i - j])