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;
}
}
