首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

动态规划 —— dp 问题-买卖股票的最佳时机含手续费

  • 25-03-07 22:41
  • 2053
  • 11768
blog.csdn.net

1. 买卖股票的最佳时机含手续费

题目链接:

714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

 


2.  算法原理

状态表示:以某一个位置为结尾或者以某一个位置为起点

 

dp[i]表示:第i天结束之后,此时的最大利润 :两种情况:

 

                                1. f[i]表示:第i天结束之后,处于买入状态,此时的最大利润

  

                                2. g[i]表示:第i天结束之后,处于卖出状态,此时的最大利润

  

2. 状态转移方程

  

在第i-1天处于买入状态,看买入状态能不能到自己,看卖出状态能不能到买入状态,另一个状态也是如此,一共4种状态

   

买入状态到卖出状态到
买入状态什么都不干-prices[i](买股票)
卖出状态+prices[i](卖股票)-fee(手续费)什么都不干

1. f[i] = max(f[i-1],g[i-1]--prices[i])

  

2. g[i] = max(g[i-1],f[i-1]+prices[i]-fee)

  

3. 初始化 :把dp表填满不越界,让后面的填表可以顺利进行

  

f[0] = --prices[0]               g[0] = 0 

4. 填表顺序 

    

本题的填表顺序是:从左往右,两个表同时填

5. 返回值 :题目要求 + 状态表示    

    

因为是要最大利润,所以买入状态不用考虑  

本题的返回值是:g[n-1]

 


3. 代码 

动态规划的固定四步骤:1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表(填表方法:状态转移方程)

                                        4. 确定返回值

  1. class Solution {
  2. public:
  3. int maxProfit(vector<int>& prices, int fee) {
  4. int n = prices.size();
  5. //1. 创建dp表
  6. vector<int>f(n);
  7. auto g=f;
  8. //2. 在填表之前初始化
  9. f[0]=-prices[0];
  10. //3. 填表(填表方法:状态转移方程)
  11. for(int i=1;i<n;i++)
  12. {
  13. f[i]=max(f[i-1],g[i-1]-prices[i]);
  14. g[i]=max(g[i-1],f[i-1]+prices[i]-fee);
  15. }
  16. //4. 确定返回值
  17. return g[n-1];
  18. }
  19. };


未完待续~ 

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览65112 人正在系统学习中
注:本文转载自blog.csdn.net的迷迭所归处的文章"https://blog.csdn.net/hedhjd/article/details/143655615"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

137
数学
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2024 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top