### LeetCode June Challenge - Day 14

Problem: LeetCode June Challenge - Day 14

Ideas:

1. Another DP problem. Let DP(i,k) be the min cost to travel from i to destination with at most k stops.
• Base cases:
• DP(dst, 0) = 0
• If there are flights from i to dst, DP(i,0) will be the min cost of those flights.
• Else cost is infinite (-1 in my code).
• Recursion: DP(i,k) will be the best option between:
• DP(i, k-1), this means not using the stop available.
• For each flight (i,d,p): p + DP(d,k-1). This means taking the flight and having 1 stop available less.

Solution:

``````class Solution {
int best(int a, int b){
if(a == -1) return b;
if(b == -1) return a;
return min(a,b);
}
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
int dp[n][K+1];

memset(dp, -1, sizeof(dp));
dp[dst] = 0;
for(vector<int>& f : flights)
if(f == dst)
dp[f] = best(f, dp[f]);

for(int k=1; k<=K; ++k){
for(int i=0; i<n; ++i)
dp[i][k] = best(dp[i][k], dp[i][k-1]);
for(vector<int>& f : flights)
if(dp[f][k-1] != -1)
dp[f][k] = best(dp[f][k], f+dp[f][k-1]);
}

return dp[src][K];
}
};
``````