787. K 站中转内最便宜的航班(动态规划)

package com.wsq.leetcode; /** * 787. K 站中转内最便宜的航班 * @author wsq * @date 2020/10/21 有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。 示例 1： 输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 输出: 200 链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops */ import java.util.Arrays; public class FindCheapestPrice { /** * 动态规划，虽然知道了动态规划解题的基本思想，但是在处理复杂问题是，还是有点无知所措 * 1.确定状态 * 最后一步：经过k-1个中转战达到 站点i-1，然后经过一步达到站点i * 子问题：计算经过k-1个中转到达i-1站点所需的最小的代价 * 2.定义转移方程 * f[i][k] = min(f[i][k], f[i][k-1] + w) * 3.初始化条件以及边界情况 * 计算src直达的状态 * 4.计算顺序 * @param n * @param flights * @param src * @param dst * @param K * @return */ public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) { // 转移方程表示，经过多少中转最小代价到达目标 int[][] f = new int[n][K + 1]; for(int i = 0; i < n; i++){ Arrays.fill(f[i], Integer.MAX_VALUE); } // 由src直达的目的地 for(int[] flight: flights){ if(flight[0] == src){ f[flight[1]][0] = flight[2]; } } // 设置出发地和目的地相同的状态，由于测试用例中存在环路，需要将src与dst相同的状态置成0 for(int i = 0; i <= K; i++){ f[src][i] = 0; } for(int i = 1; i <= K; i++){ for(int[] flight: flights){ if(f[flight[0]][i-1] != Integer.MAX_VALUE){ f[flight[1]][i] = Math.min(f[flight[1]][i], f[flight[0]][i-1] + flight[2]); } } } return f[dst][K] == Integer.MAX_VALUE ? -1 : f[dst][K]; } }