787. K 站中转内最便宜的航班 图类和边相关的dp

本文主要是介绍787. K 站中转内最便宜的航班 图类和边相关的dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解题思路

1. 状态定义，$dp[u][v][k]$代表从城市$u$到达城市$v$，最多经过$k$个中转站得到的最小的距离。
2. 本题中，源城市确定，显然这里上面定义状态的第一维$u$就不需要了，所以我们的状态$dp[v][k]$代表从城市$src$到达城市$v$，最多经过$k$个中转站得到的最小的距离。
3. 初始状态，$dp[src][i]=0,0<=i<k$，$dp[flights[i][1]][0]=flight[i][2],0<=i<n$，其它的设置为$INT\_MAX$。
4. 最外层循环，$1<=k<=K$，内层循环，扫描所有的边。
5. 时间复杂度$O(K\ast E)$，$E$为边的个数。
6. 空间复杂度$O(n\ast k)$，觉得可以和背包问题一样优化到一维。
7. 官方代码

代码

class Solution {
public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {vector<vector<int>>dp(n, vector<int>(K+1, INT_MAX));for (int i = 0; i <= K; i++){dp[src][i] = 0;}for (vector<int>& flight : flights){if (flight[0] == src){dp[flight[1]][0] = flight[2];}}for (int i = 1; i <= K; i++){int nowBegin = 0;int nowEnd = 0;for (vector<int> &flight : flights){nowBegin = flight[0];nowEnd = flight[1];if (dp[nowBegin][i - 1] != INT_MAX){dp[nowEnd][i] = min(dp[nowBegin][i - 1] + flight[2], dp[nowEnd][i]);}}}return dp[dst][K] == INT_MAX ? -1 : dp[dst][K];}
};

这篇关于787. K 站中转内最便宜的航班 图类和边相关的dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---