Tag

【遞歸】【記憶化搜索】【動態規劃】【數組】【2023-12-08】

---

題目來源

2008. 出租車的最大盈利

---

解題思路

以下題解與思路參考 教你一步步思考動態規劃：從記憶化搜索到遞推（Python/Java/C++/Go/JS/Rust）。

尋找子問題

假設 n = 9。我們要解決的問題是從 1 開車到 9 最多可以賺多錢。

會有以下兩種情況出現：

• 情況一：如果沒有乘客在 9 下車，或者我們不搭載在 9 下車的乘客，那么問題就變成：從 1 開車到 8 最多可以賺多少錢；
• 情況二：如果有至少一位乘客在 9 下車，我們可以枚舉載哪位乘客。假設所載乘客在 5 上車，那么從 5 到 9 不能載其它乘客（題目要求同時最多只能接一個訂單），問題變成：從 1 到 5 最多可以賺多少錢。

以上兩種情況都會將原問題變成 「和原問題相似的、規模更小的子問題」，這意味著可以使用遞歸來解決問題。

方法一：遞歸

思路

遞歸函數定義為 dfs(i)，表示從 1 開車到 i 最多可以賺多少錢。

情況一中問題變為：從 1 開車到 i-1 最多可以賺錢多少，有轉移關系式：

$$dfs(i)=dfs(i?1)$$

在情況二中，我們可以枚舉搭載哪位乘客，取其中最賺錢的方案，有轉移關系式：

$$dfs(i)=max(dfs(start)+i?start+tip)$$
其中，start 表示到 i 的乘客的上車點，tip 為從 start 到 i 這一段路的小費。

以上兩種情況取最大值得到 dfs(i)，即

$$dfs(i)=max(dfs(i?1),max(dfs(start)+i?start+tip))$$

遞歸邊界：dfs(1) = 0，因為沒有在 1 下車的乘客。

遞歸入口：dfs(n)，也是最后需要返回的答案。

算法

在實現中，將 rides 數組按照下車點進行分組，方便枚舉所有在 i 下車點下車的乘客。在分組中，使用 pair 記錄每一個分組中的 start 和 end - start + tip。

class Solution {
public:long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {vector<vector<pair<int, int>>> g(n+1);for (auto ride : rides) {int start = ride[0], end = ride[1], tip = ride[2];g[end].push_back(make_pair(start, end - start + tip));}function<long long(int)> dfs = [&](int i) -> long long {if (i == 0) {return 0;}long long res = dfs(i - 1);for (auto [s, t] : g[i]) {res = max(res, dfs(s) + t);}return res;};return dfs(n);}
};

該方法超時。

方法二：遞歸+記錄數組=記憶化搜索

思路

由于在遞歸中存在某些 dfs(i) 重復計算的問題，因此可以使用一個數組 memo 記錄計算結果，在遞歸中使用數據記錄計算出的值的方法被稱為「記憶化搜索」。

算法

class Solution {
public:long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {vector<vector<pair<int, int>>> g(n+1);for (auto ride : rides) {int start = ride[0], end = ride[1], tip = ride[2];g[end].push_back(make_pair(start, end - start + tip));}vector<long long> memo(n+1, -1);    // -1 表示沒有計算過function<long long(int)> dfs = [&](int i) -> long long {if (i == 0) {return 0;}auto& res = memo[i];    // 這里是引用，因為后面需要將更新后的 res 更新到 memo 中if (res != -1) {return res;}res = dfs(i - 1);for (auto [s, t] : g[i]) {res = max(res, dfs(s) + t);}return res;};return dfs(n);}
};

復雜度分析

時間復雜度：$O(n+m)$。

空間復雜度：$O(n+m)$。

方法三：動態規劃（遞推）

思路

將遞歸對應翻譯為動態規劃。

狀態方程 f[i] 表示從 1 開車到 i 最多可以賺多少錢。

狀態轉移關系：

$$f[i]=max(f[i?1],max(f[start]+i?end+tip))$$

base case：f[1] = 0。

最后返回：return f[n]。

算法

class Solution {
public:long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {vector<vector<pair<int, int>>> g(n+1);for (auto ride : rides) {int start = ride[0], end = ride[1], tip = ride[2];g[end].push_back(make_pair(start, end - start + tip));}vector<long long> f(n+1);    for (int i = 2; i <= n; ++i) {f[i] = f[i-1];for (auto [s, t] : g[i]) {f[i] = max(f[i], f[s] + t);}}return f[n];}
};

復雜度分析

時間復雜度：$O(n+m)$，其中 $m$ 是 rides 的長度，n 是地點數目。動態規劃轉移需要 $O(n)$ 的時間，查詢乘客信息需要 $O(m)$ 的時間。

空間復雜度：$O(n+m)$。

---

寫在最后

如果您發現文章有任何錯誤或者對文章有任何疑問，歡迎私信博主或者在評論區指出 💬💬💬。

如果大家有更優的時間、空間復雜度的方法，歡迎評論區交流。

最后，感謝您的閱讀，如果有所收獲的話可以給我點一個 👍 哦。