力扣(LeetCode)2008. 出租车的最大盈利(C语言)
一、环境说明
- 本文是 LeetCode 2008题 : 出租车的最大盈利，使用c语言实现。
- 动态规划。
- 测试环境:Visual Studio 2019。
二、代码展示
#define Max(a,b) ((a)>(b)?(a):(b))
int cmp(const void *a,const void *b){
return (*((int**)a))[1] - (*((int**)b))[1];//按照end升序
}
long long maxTaxiEarnings(int n, int** rides, int ridesSize, int* ridesColSize){
qsort(rides,ridesSize,sizeof(rides[0]),cmp);//按照end升序
int i = 1,j=0;//遍历的两个位置
long long dp[n+1];//最大dp[n]
memset(dp,0,sizeof(long long)*n);//初始化dp为0
while(i<=n){//一直遍历到dp[n]
dp[i]=dp[i-1];
while(j<ridesSize&&i==rides[j][1]){//j用于遍历rides。当终点i==rides[j][1]时，说明需要更新dp了。
int end =rides[j][1];//终点
int start = rides[j][0];//起点
int tips = rides[j][2];//小费
dp[i]=Max(dp[i],dp[start]+end - start +tips);
j++;//找下一个j//这里可以二分查找优化//参考1235题官解。
}
i++;
}
return dp[n];
}
三、思路分析
- 动态规划。
- 分析怎么设计 d p dp dp。区间动态规划的较好处理是：遍历 r i d e s rides rides，找目前最早的结束地点 e n d end end。
- 同时遍历 n n n和 r i d e s rides rides，用 i i i表示 n n n当前位置，用 j j j表示 r i d e s rides rides当前位置。
- 我们对 r i d e s rides rides按 e n d end end升序快排，当前位置 j j j就是目前最早的 e n d end end。
- 记 f [ i ] f[i] f[i]为 i i i位置前的最大盈利。对于位置 i i i，最大盈利 f [ i ] f[i] f[i]可能等于 f [ i − 1 ] f[i-1] f[i−1]，也可能等于 f [ j ] + e n d − s t a r t + t i p s f[j]+end-start+tips f[j]+end−start+tips，所以设计 f [ i ] = M a x ( f [ i − 1 ] , f [ j ] + e n d − s t a r t + t i p s ) f[i]=Max(f[i-1],f[j]+end-start+tips) f[i]=Max(f[i−1],f[j]+end−start+tips)。 j j j是以 i i i作为 e n d end end的一个起始地点。
- 提示： i i i之前上车的顾客，可能不止一个人在 i i i下车。所以我们用 j j j遍历 r i d e s rides rides，确保每个顾客都被考虑。
四、代码分析
- 理解思路很重要！
- 欢迎读者在评论区留言，作为日更博主，看到就会回复的。
五、AC
第一次双百。
六、复杂度分析
- 时间复杂度: O ( n + m l o g m ) O(n+mlogm) O(n+mlogm) , n n n是 n n n的大小， m m m是 r i d e s rides rides的大小。快排 r i d e s rides rides，遍历字符串 n 、 r i d e s n、rides n、rides的时间复杂度是 O ( m l o g m + n + m ) O(mlogm+n+m) O(mlogm+n+m)。
- 空间复杂度: O ( n ) O(n) O(n), d p [ n ] dp[n] dp[n]的空间复杂度 O ( n ) O(n) O(n)