一、题目

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 toi 抵达 pricei。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

点击查看原题
难度级别： 中等

二、思路

1）动态规划

使用数组dp[i][j]代表经历i-1次中转，从src到j节点的最少花费，可以得到状态转移方程：

优化：由于只依赖i-1的状态，可以优化为两个一维数组

三、代码

1）动态规划

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[][] dp = new int[k+2][n];
        for (int i = 0; i <= k+1; ++i) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][src] = 0;
        for (int i = 1; i <= k+1; i++) {
            for (int[] flight : flights) {
                if (dp[i-1][flight[0]] != Integer.MAX_VALUE) {
                    dp[i][flight[1]] = Math.min(dp[i-1][flight[0]] + flight[2], dp[i][flight[1]]);
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < k+2; i++) {
            ans = Math.min(ans, dp[i][dst]);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

时间复杂度为O((flights.length + n)*k)，空间复杂度为O(n*k)
优化代码如下：

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] dp = new int[n];
        int ans = Integer.MAX_VALUE;
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[src] = 0;
        for (int i = 1; i <= k+1; i++) {
            int[] temp = new int[n];
            Arrays.fill(temp, Integer.MAX_VALUE);
            for (int[] flight : flights) {
                if (dp[flight[0]] != Integer.MAX_VALUE) {
                    temp[flight[1]] = Math.min(dp[flight[0]] + flight[2], temp[flight[1]]);
                }
            }
            dp = temp;
            ans = Math.min(ans, dp[dst]);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

时间复杂度为O((flights.length + n)*k)，空间复杂度为O(n)