【算法训练营day49】LeetCode121. 买卖股票的最佳时机 LeetCode122. 买卖股票的最佳时机II
2023-04-18 15:20:32 时间
LeetCode121. 买卖股票的最佳时机
题目链接:121. 买卖股票的最佳时机
独上高楼,望尽天涯路
感觉贪心会更简单,动态规划反而搞复杂了对于这道题。
慕然回首,灯火阑珊处
第一次看题解还是挺难理解的,所以这次写的规范一点。
- 确定dp数组及其下标的含义
dp[i][0]
表示的是第i天持有股票所得最多现金,通俗一点,就是截止到第i天所能买入股票花费的最少现金。
dp[i][1]
表示的是第i天不持有股票所得最多现金,通俗一点,就是截止到第i天卖出股票所赚得的最多现金。
截止是一个关键词,意思是不一定是第i天买入或卖出股票,而是包含第i天及之前所有时间的买入卖出操作。
- 确定递推公式
dp[i][0]
可以由两个状态推出来,一个是昨天及之前的买入价格更低;另一个是今天的买入价格更低;我们取最好的那个就行。
dp[i][1]
也可以由两个状态推出来,一个是昨天及之前已经完成的买入卖出操作赚的更多;另一个是用今天的价格卖出,买入价格用昨天及之前最低的买入价格,赚的更多;我们还是取最好的那个就行。
- dp数组如何初始化
dp[0][0]
表示第0天最低的买入价格,只能是第0天的买入价格。
dp[0][1]
表示第0天卖出所赚得的最多现金,因为第0天不能卖出,所以为0。
- 确定遍历顺序
从前向后遍历prices数组即可。
- 举例推导dp数组
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 1) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(2));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
}
return dp[prices.size() - 1][1];
}
};
LeetCode122. 买卖股票的最佳时机II
题目链接:122. 买卖股票的最佳时机II
独上高楼,望尽天涯路
没什么思路。
慕然回首,灯火阑珊处
看完题解,猪脑过载,得慢慢消化...
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(2));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < prices.size(); 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]);
}
return dp[prices.size() - 1][1];
}
};
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击