北京网站建设市场,织梦高清电影网站模板,安卓商城,电子商务毕业设计设计网站建设文章目录 Tag题目来源解题思路方法一#xff1a;递归方法二#xff1a;递归记录数组记忆化搜索方法三#xff1a;动态规划#xff08;递推#xff09; 写在最后 Tag
【递归】【记忆化搜索】【动态规划】【数组】【2023-12-08】 题目来源
2008. 出租车的最大盈利 解题思路… 文章目录 Tag题目来源解题思路方法一递归方法二递归记录数组记忆化搜索方法三动态规划递推 写在最后 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 最多可以赚钱多少有转移关系式 d f s ( i ) d f s ( i − 1 ) dfs(i) dfs(i - 1) dfs(i)dfs(i−1)
在情况二中我们可以枚举搭载哪位乘客取其中最赚钱的方案有转移关系式 d f s ( i ) m a x ( d f s ( s t a r t ) i − s t a r t t i p ) dfs(i) max(dfs(start) i - start tip) dfs(i)max(dfs(start)i−starttip) 其中start 表示到 i 的乘客的上车点tip 为从 start 到 i 这一段路的小费。
以上两种情况取最大值得到 dfs(i)即 d f s ( i ) m a x ( d f s ( i − 1 ) , m a x ( d f s ( s t a r t ) i − s t a r t t i p ) ) dfs(i) max(dfs(i - 1), max(dfs(start) i - start tip)) dfs(i)max(dfs(i−1),max(dfs(start)i−starttip))
递归边界dfs(1) 0因为没有在 1 下车的乘客。
递归入口dfs(n)也是最后需要返回的答案。
算法
在实现中将 rides 数组按照下车点进行分组方便枚举所有在 i 下车点下车的乘客。在分组中使用 pair 记录每一个分组中的 start 和 end - start tip。
class Solution {
public:long long maxTaxiEarnings(int n, vectorvectorint rides) {vectorvectorpairint, int g(n1);for (auto ride : rides) {int start ride[0], end ride[1], tip ride[2];g[end].push_back(make_pair(start, end - start tip));}functionlong 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, vectorvectorint rides) {vectorvectorpairint, int g(n1);for (auto ride : rides) {int start ride[0], end ride[1], tip ride[2];g[end].push_back(make_pair(start, end - start tip));}vectorlong long memo(n1, -1); // -1 表示没有计算过functionlong 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(nm) O(nm)。
空间复杂度 O ( n m ) O(nm) O(nm)。
方法三动态规划递推
思路
将递归对应翻译为动态规划。
状态方程 f[i] 表示从 1 开车到 i 最多可以赚多少钱。
状态转移关系 f [ i ] m a x ( f [ i − 1 ] , m a x ( f [ s t a r t ] i − e n d t i p ) ) f[i] max(f[i-1], max(f[start] i - end tip)) f[i]max(f[i−1],max(f[start]i−endtip))
base casef[1] 0。
最后返回return f[n]。
算法
class Solution {
public:long long maxTaxiEarnings(int n, vectorvectorint rides) {vectorvectorpairint, int g(n1);for (auto ride : rides) {int start ride[0], end ride[1], tip ride[2];g[end].push_back(make_pair(start, end - start tip));}vectorlong long f(n1); 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 ) O(nm) O(nm)其中 m m m 是 rides 的长度n 是地点数目。动态规划转移需要 O ( n ) O(n) O(n) 的时间查询乘客信息需要 O ( m ) O(m) O(m) 的时间。
空间复杂度 O ( n m ) O(nm) O(nm)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
