787. Cheapest Flights Within K Stops

Link

Solution

dp[k][d] -> denote the min cost of flights from src to d with k moves (k-1 stop)

Assume there is a ticket: from t -> d, cost w, then

dp[k][d] = Math.min(dp[k][d], w + dp[k-1][t]);

K stops means K+1 moves

So the DP array shall be int[K+2][n]

 public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        //Collect flights and price
        int[][] dp = new int[K+2][n];      
        for(int[] row : dp){
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        for(int i = 0; i <= K+1; i++){
            dp[i][src] = 0;
        }
        
        for(int i = 1; i <= K+1 ; i++){
            for(int[] flight : flights){
                int from = flight[0];
                int to = flight[1];
                int cost = flight[2];
                
                if(dp[i-1][from] != Integer.MAX_VALUE){
                    dp[i][to] = Math.min(dp[i][to], cost + dp[i-1][from]);
                }
            }
        }
        return dp[K+1][dst] == Integer.MAX_VALUE ? -1 : dp[K+1][dst];
    }