LeetCode 787 Cheapest Flights Within K Stops

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

概述

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

动态规划法

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

历史错误:

  1. 忘记 base case src == dst;
  2. 忘记处理子问题 helper返回为 -1 的情况;
  3. base case 的顺序问题;
  4. 我们这里使用 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 算法啦,唯一需要注意的是这里有节点个数限制,估计得改一下,懒得写了。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/