K站中转内最便宜的航班

题目

思路

• 思路一：递归
• 思路二：备忘录
• 思路三：动态规划

• 思路四：优化dp数组的动态规划

  代码

  ```java //1.暴力递归 public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

    int res = recur(flights, src, dst, K);
    return res == Integer.MAX_VALUE ? -1 : res;

  }

  public int recur(int[][] flights, int src, int dst, int k) {

    if (k < 0 && src != dst) return Integer.MIN_VALUE;
    if (k >= -1 && src == dst) return 0;
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < flights.length; i++) {
        if (flights[i][1] == dst) {
            int temp = recur(flights, src, flights[i][0], k - 1) + flights[i][2];
            res = temp > 0 ? Math.min(res, temp) : res;
        }
    }
    return res;
  

  }

  //2.备忘录 int[][] dp; public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

    dp = new int[n][K + 2];
    int res = recur(flights, src, dst, K);
    return res == Integer.MAX_VALUE ? -1 : res;
  

  }

  public int recur(int[][] flights, int src, int dst, int k) {

    if (k < 0 && src != dst) return Integer.MIN_VALUE;
    if (k >= -1 && src == dst) return 0;
    if (dp[dst][k + 1] != 0) return dp[dst][k + 1];
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < flights.length; i++) {
        if (flights[i][1] == dst) {
            int temp = recur(flights, src, flights[i][0], k - 1) + flights[i][2];
            res = temp > 0 ? Math.min(res, temp) : res;
        }
    }
    dp[dst][k + 1] = res;
    return res;
  

  }

  //3.动态规划 public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

    int[][] dp = new int[n][K + 2];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < K + 2; j++) {
            dp[i][j] = Integer.MAX_VALUE;
        }
    }
    for (int i = 0; i < K + 2; i++) {
        dp[src][i] = 0;
    }
    for (int j = 1; j < K + 2; j++) {
        for (int[] flight : flights) {
            if (dp[flight[0]][j - 1] != Integer.MAX_VALUE) {
                dp[flight[1]][j] = Math.min(
                    dp[flight[1]][j], dp[flight[0]][j - 1] + flight[2]);
            }
        }
    }
    return dp[dst][K + 1] == Integer.MAX_VALUE ? - 1 : dp[dst][K + 1];
  

  }

  //4.动态规划，优化dp数组，使用两个一维数组进行优化 public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

    int[] dp = new int[n];
    int[] prevDp = new int[n];
    for (int i = 0; i < n; i++) {
        dp[i] = Integer.MAX_VALUE;
        prevDp[i] = Integer.MAX_VALUE;
    }
    prevDp[src] = 0;
    dp[src] = 0;
    for (int j = 1; j < K + 2; j++) {
        for (int[] flight : flights) {
            if (prevDp[flight[0]] != Integer.MAX_VALUE) {
                dp[flight[1]] = Math.min(dp[flight[1]], prevDp[flight[0]]+ flight[2]);
            }
        }
        for (int i = 0; i < n; i++) {
            prevDp[i] = dp[i];
        }
    }
    return dp[dst] == Integer.MAX_VALUE ? - 1 : dp[dst];
  

  }

``` K站中转内最便宜的航班