[数据结构与算法]LeetCode.787 K 站中转内最便宜的航班

原题

https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/

思路

动态规划
看到此题，直观的思路有 DFS 和 动态规划
这里只说下动态规划，动态规划最难的就是定义动态规划方程

定义f[t][i]表示行走t步从src站到达i站的所需最小花费
定义f[t-1][j]表示行走t-1步从src站到达j站的所需最小花费
定义cost(j,i)表示从j站到i站的花费，即flight[3]
=> 则推导出 f[t][i] = f[t-1][j] + cost(j,i)
=> 则f[][] 的长度分别是f[t+2][n]
解释：长度t+2,最多有t+1个元素，也就是最多走t+1步；n也就是题意中最多n个站
由于求最小花费，需先将f[t+2][n]中的元素都设置为一个较大值
注意特殊值：f[0][src]=0 行走0步到达src站的花费，即自己到达自己
接下来开始枚举即可，数据的突破口就是f[0][src]

题解

package com.leetcode.code;

import java.util.Arrays;

public class Code787 {

    public static void main(String[] args) {

    }

    static int INF = 10000 * 101 + 1;

    public static int findCheapestPrice1(int n, int[][] flights, int src, int dst, int k) {
//        f[t][i] 表示 行走t步 从src站到i站 的花费
//        k+2为长度，实际最大为k+1，经过k站，需要走k+1条边
        int[][] f = new int[k+2][n];
//        将f数组中的每个元素都填充为最大值
        for (int i = 0; i < k+2; i++) {
            Arrays.fill(f[i], INF);
        }
//		  特殊值
        f[0][src] = 0;
//		  从走第1步开始
        for (int t = 1; t < k+2; t++) {
            for (int[] flight : flights) {
//                起点
                int j = flight[0];
//                终点
                int i = flight[1];
//                起点到终点的花费
                int cost = flight[2];
//                行走t步到达i站的所需最小花费
                f[t][i] = Math.min(f[t][i], f[t-1][j]+cost);
            }
        }
        int res = INF;
//        找到出一条【最多】经过 k 站中转的路线
//        src != dst 所以t从1开始
        for (int t = 1; t < k+2; t++) {
            res = Math.min(res, f[t][dst]);
        }

        return res == INF ? -1 : res;
    }



}