172、【动态规划】leetcode ——714. 买卖股票的最佳时机含手续费 (C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:714. 买卖股票的最佳时机含手续费
解题思路
本题和 122. 买卖股票的最佳时机 II(贪心算法+动态规划) 的区别在于含有一个收费,只需要在最后卖出时候扣除手续费后再比较即可。
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<vector<int>> dp(n + 1, vector<int>(2));
dp[0][0] = -prices[0], dp[0][1] = 0;
for(int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
}
return dp[n - 1][1];
}
};
注意:最后返回的可以不为return max(dp[n - 1][0], dp[n - 1][1])
,因为会有扣除手续费,可能会导致卖出去后扣得费用更多所以返回这两个中的最大值。但是,由于dp[i][1]获取时,已经是max(dp[i - 1][1], dp[i - 1][0] + prices[i]),也就是上一次没有卖的时候和这次进行买卖后比较出最大值。所以,此时已经包含之前已经会将的情况,不会做亏本的买卖。
相关文章
- 【C/C++学院】0817-递归汉诺塔 双层递归 /CPP结构体 /面向过程与面向对象的编程模式/类的常识共用体实现一个类的特征/QT应用于类以及类的常识
- 传智播客c/c++公开课学习笔记--C语言与木马恶意代码分析和360安全防护揭秘
- 编程笔试(解析及代码实现):猴子吃桃。猴子第一天吃了若干个桃子,当即吃了一半,还不解馋,又多吃了一个…的C++、Java、Python、C#等语言代码实现
- c++容器vector
- C++ 强转注意问题
- C++学习心得与c语言到c++衔接技巧
- Leetcode 搜索旋转排序数组(执行用时: 0 ms , 在所有 C++ 提交中击败了 100.00% 的用户)
- LeetCode 整数转罗马数字(执行用时: 12 ms , 在所有 C++ 提交中击败了 32.38% 的用户)
- Leetcode 两数之和 C / C++
- LeetCode 罗马数字转整数(执行用时: 16 ms , 在所有 C++ 提交中击败了 49.87% 的用户)
- c++ vector 初始化_C++--vector()的用法
- 浅谈C++多态性
- AI模型C++部署:ubuntu安装Cython并使用C/C++调用python动态库【附加c++与python互相调用算法demo程序接口的源码】
- c++ vector C++ vector存放结构体 并且排序
- C++语言虚函数表实现多态原理(六十七)
- C++关键字typeid获取int/unsigned long等类型(三十一)
- VS2019: C++代码静态分析改进和更新
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色