LeetCode 787. K 站中转内最便宜的航班

1、题目

image.png

2、分析

这个题目就是求最小加权路径的问题。
递归求法：

image.png

就是求，从src，用k - 1步，到达s1、s2。

动态规划法：
主要是定义好dp数组dp[t][i]表示中src经过航班t，到达站点i的最少价格

3、代码

递归代码：

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[][] memo = new int[n][k + 2];
        return dp(flights, src, dst, k + 1, memo); //k+1是因为经过k个站点，需要k+1条路径
    }

    private int dp(int[][] flights, int src, int dst, int k, int[][] memo){
        if(src == dst) return 0;
        if(k == 0) return -1;
        if(memo[dst][k] != 0) return memo[dst][k];
        int res = Integer.MAX_VALUE;
        for(int[] flight: flights){
            if(flight[1] == dst){
                int sub = dp(flights, src, flight[0], k - 1, memo);
                if(sub != -1)
                    res = Math.min(res, sub + flight[2]);
            }
        }
        memo[dst][k] = res == Integer.MAX_VALUE ? -1 : res;
        return memo[dst][k];
    }
}

动态规划代码：

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int max = 10000 * 101 + 1;
        int[][] dp = new int[k + 2][n];
        for(int i = 0; i < k + 2; i++){
            Arrays.fill(dp[i], max);
        }
        dp[0][src] = 0;
        for(int t = 1; t <= k + 1; t++){
            for(int[] flight : flights){
                int j = flight[0]; int i = flight[1]; int cost = flight[2];
                dp[t][i] = Math.min(dp[t][i], dp[t - 1][j] + cost); //和dp[t][i]比较，是因为可能好很多条线路到目的地i，有的有解，有的无解。需要比较保存价格最小的那个。
            }
        }
        int res = max;
        for(int i = 0; i <= k + 1; i++){
            res = Math.min(res, dp[i][dst]);
        }
        return res == max ? -1 : res;
    }
}