23.01.26 Today’s Leetcode

787. Cheapest Flights Within K Stops (medium)

DP는 너무 어렵다. Dynamic Programming이라는 Problem Solving 기법이에요. DFS로는 처음에는 풀었으나, DP로 해야만 풀림.

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        cost = [{} for y in range(n)]
        for f, t, price in flights:
            cost[f][t] = price

        def dfs(cur, target, count):
            if cur == target:
                return 0
            if count < 0:
                return -1
            res = 10**9
            for to in cost[cur].keys():
                temp = dfs(to, target, count - 1)
                if temp != -1:
                    res = min(res, temp + cost[cur][to])
            if res == 10**9:
                return -1
            return res
        return dfs(src, dst, k)

DP를 이용해서 푼 JAVA code

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // dp[i][j] means that cheapest cost with ith stops from j to src
        int[][] dp = new int[k + 2][n];

        for(int i = 0; i <= k + 1; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);    
        }

        // fly from src to src cost 0
        for(int i = 0; i <= k + 1; i++){
            dp[i][src] = 0;    
        }
        
        for(int i = 1; i <= k + 1; i++)
            for(int[] f: flights)
                if(dp[i - 1][f[0]] != Integer.MAX_VALUE) 
                    dp[i][f[1]] = Math.min(dp[i][f[1]], dp[i-1][f[0]] + f[2]);
        return dp[k + 1][dst] == Integer.MAX_VALUE ? -1 : dp[k + 1][dst];
    }
}