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] = 0;
        for(vector<int>& f : flights)
            if(f[1] == dst)
                dp[f[0]][0] = best(f[2], dp[f[0]][0]);

        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[1]][k-1] != -1)
                    dp[f[0]][k] = best(dp[f[0]][k], f[2]+dp[f[1]][k-1]);
        }

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