LeetCode 787 Cheapest Flights Within K Stops

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2022-02-19 18:04:28
    编辑于：2022-02-19 18:16:33
    浏览量：980

概述

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

动态规划法

乍一看我们需要三维的状态，实际上终点是不需要的，该题依然是两个状态：起始点和剩余站。

历史错误：

忘记 base case src == dst；
忘记处理子问题 helper返回为 -1 的情况；
base case 的顺序问题；
我们这里使用 map 来作为 graph，但是别忘了如果访问了不存在的值其会自动创建一个项，那么我们应该注意剔除掉这种项。

另外注意，这虽然是图，但是我们并没有记录节点是否重复访问过，而是仅依赖 k，如果 k 很大，将导致 TLE，解决方法很简单，k = min(k, 节点个数)

class Solution {
public:
    unordered_map<int, unordered_map<int, int>> graph;
    unordered_map<int, unordered_map<int, int>> dp;  // fron i within k
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        for (auto& f : flights) graph[f[0]][f[1]] = f[2];
        return helper(src, dst, k);
    }
    
    int helper(int i, int j, int k) {
        if (i == j) return 0;  // 忘记 base case src == dst；
        if (k == 0) {  // base case 的顺序问题；
            if (graph[i][j] != 0) return graph[i][j];
            else return -1;
        }
        if (dp[i][k] != 0) return dp[i][k];
        int res = INT_MAX;
        for (auto iter = graph[i].begin(); iter != graph[i].end(); ++ iter) {
            if (iter->second == 0) continue;  // 我们这里使用 map 来作为 graph，但是别忘了如果访问了不存在的值其会自动创建一个项，那么我们应该注意剔除掉这种项。
            int temp = helper(iter->first, j, k - 1);
            if (temp == -1) continue;  // 忘记处理子问题 helper返回为 -1 的情况；
            res = min(res, iter->second + temp);
        }
        if (res == INT_MAX) res = -1;
        dp[i][k] = res;
        return res;
    }
};

k + 1 后，我们的 base case 可以写的更加好看，此时 k 不再代表中转站个数，而是代表飞行次数：

class Solution {
public:
    unordered_map<int, unordered_map<int, int>> graph;
    unordered_map<int, unordered_map<int, int>> dp;  // fron i within k
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        for (auto& f : flights) graph[f[0]][f[1]] = f[2];
        return helper(src, dst, k + 1);
    }
    
    int helper(int i, int j, int k) {
        if (i == j) return 0;
        if (k == 0) return -1;
        if (dp[i][k] != 0) return dp[i][k];
        int res = INT_MAX;
        for (auto iter = graph[i].begin(); iter != graph[i].end(); ++ iter) {
            if (iter->second == 0) continue;
            int temp = helper(iter->first, j, k - 1);
            if (temp == -1) continue;
            res = min(res, iter->second + temp);
        }
        if (res == INT_MAX) res = -1;
        dp[i][k] = res;
        return res;
    }
};

Dijkstra 算法

略最短路径自然少不了我 Dijkstra 算法啦，唯一需要注意的是这里有节点个数限制，估计得改一下，懒得写了。

Links: leetcode-787-cheapest-flights-within-k-stops