前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >解锁动态规划的奥秘:从零到精通的创新思维解析(9)

解锁动态规划的奥秘:从零到精通的创新思维解析(9)

作者头像
用户11295429
发布于 2025-04-18 02:16:47
发布于 2025-04-18 02:16:47
3900
代码可运行
举报
文章被收录于专栏:王的博客专栏王的博客专栏
运行总次数:0
代码可运行

前言:

小编在前几日写了关于动态规划中的多状态dp的问题,此时小编将会讲述一个动态规划我们常常会遇到的一类问题——股票问题,股票问题就类似小编上一篇所讲述的粉刷房子的问题,可以通过一个二维的dp表来代替多个一维的dp表。买卖股票算是一个很经典的问题了,下面小编简单介绍一下买卖股票问题。

“买卖股票问题”作为动态规划的经典案例,不仅在编程竞赛中频繁出现,也是面试中的常考题目。这类问题以其现实背景的贴近性和解法的多样性著称,不仅考察了对动态规划核心思想的掌握,还能帮助我们深入理解状态转移、子问题划分以及优化策略。

从最基本的一次买卖股票问题,到允许多次买卖甚至设置冷却期和手续费的复杂变体,每一步都体现了动态规划在不同约束条件下的灵活性与精妙性。本篇内容将以逐步深入的方式,剖析买卖股票问题的不同场景,通过数学建模和代码实现,让读者能够全面掌握这一重要的动态规划应用,并在实际问题中灵活运用。

1.买卖股票的最佳时机含冷却期

1.1.题目来源

本题来自于力扣,下面小编给出相应的链接;309. 买卖股票的最佳时机含冷冻期 - 力扣(LeetCode)

1.2.题目分析

本题的内容比较短,但是包含了许多内容,下面小编简单的概述一下:此时题目给与我们一个数组,此时这个数组里面的内容表示的是第i天时的股票价格,此时我们可以选择不购买当天的股票,或者是购买当天的股票,也可以选择把手头上的股票卖出,只不过本题多了一个限制——我们在卖出股票的第二天是无法购买股票的,因为有1天的冷却期。此时我们需要设计一个算法,这个算法是帮助我们计算我们在买卖股票的最大理论,这便是这个题目让我们去撰写的函数,并且值得一提的是,我们是不可以去参与多笔交易(我们必须在下次购买股票的时候把手头上的股票先卖出去)。

1.3.思路讲解
1.状态表示

此时我们需要一个二维的dp表来表示此时的状态,本题目到是让我们写dp表状态的时候很好入手,无非就是表示买入,可交易,冷冻期三种状态罢了,此时我们可以用dp表的三列来分别表示此时的状态。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
dp[i][0]; //第i天结束以后,进入"买入"状态,此时的最大理论。
dp[i][1]; //第i天结束以后,进入"可交易"状态,此时的最大理论。
dp[i][2]; //第i天结束以后,进入"冷冻期"状态,此时的最大理论。
1.2.状态转换方程

此时的状态转换方程其实是本题目的最大难点,因为从题目给定我们的信息我们就可以知道,本题三个状态关系十分的密切,针对于这种情况,此时小编引入了一个小小的模型——状态机。

状态机:动态规划问题中的核心模型

在动态规划的解决方案中,状态机(State Machine)是一个重要的抽象模型,尤其适用于解决问题有明确状态和状态之间的转移规则时。买卖股票问题是应用状态机的典型场景,通过状态机的建模,我们可以清晰地表达状态的变化和转移,从而找到问题的最优解。

状态机是一个由状态(State)状态转移(State Transition)组成的系统。在动态规划中,状态机通常用来描述问题在不同时间点的可能状态,以及这些状态之间如何通过某种操作发生转移。

在买卖股票问题中,状态机可以用来表示每一天结束时的可能状态,比如“手上有股票”或“手上没有股票”,并用状态转移来表达买入、卖出或保持现状的操作。

下面小编通过图片的方式展示一下状态机的使用方法。

此时我们先来看买入状态,当前一天是买入状态的时候,证明此时已经买入了股票,所以我们可以选择卖出股票进入冷冻期状态;或者是啥也不干,当天还是买入状态。

此时我们在看冷冻期状态,此时如果前一天是冷冻期状态,那么根据题意,第二天仅仅只能是进入可交易状态(手里没股票)。

最后我们再看可交易的状态。如果第二天是可交易状态,那么我们也是有两种选择,分别是:从可交易状态进入买入状态,此时我们需要付费;也可以选择啥也不干,因为股票的价格不好,所以当天还是可交易状态。

所以我们根据状态机便可以很好的去列状态转换方程,如下所示:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
dp[i][0] - max(dp[i - 1][0],dp[i - 1][1] - price[i]);//根据箭头指过来的方向
dp[i][1] = max(dp[i - 1][2],dp[i - 1][1]);
dp[i][2] = max(dp[i - 1][0] + price[i]);
3.初始化

初始化是我们在写状态转换方程的时候最主要注意的细节问题,此时我们可以知晓此时当我们选择第一个元素的时候就会出现数组越界的问题,针对于这种问题,小编认为多开辟一行作为虚拟节点是最省事的方式,只不过此时我们需要注意虚拟节点需要填入什么。根据题目,我们可以知道在买入状态的时候,此时手里必须有股票,所以dp[I] [0]应该是-price[i - 1](注意下标的映射问题哦),其他的两个位置为0即可。

4.填表顺序

从上到下,从左到右。

5.返回值

根据题目,我们仅需返回最后一个位置中最大的元素即可。

1.4.代码实操

此时我们需要设置好一个dp表,此时这个dp表要比原先给定我们的数组要多开辟一行存入虚拟节点。并且给相应的位置进行初始化即可。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int n = prices.size();
vector<vector<int>> dp(n,vector<int>(3,0));
dp[0][0] = -prices[0];

此时我们再根据状态转换方程,通过循环填写数据即可。(一定要注意下标的映射)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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][2]);
    dp[i][2] = dp[i-1][0] + prices[i];
}

最后,我们返回最后一个位置最大的数据即可。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 return max(dp[n - 1][1],dp[n - 1][2]);
1.5.代码展示
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n,vector<int>(3,0));
        dp[0][0] = -prices[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][2]);
            dp[i][2] = dp[i-1][0] + prices[i];
        }
        return max(dp[n - 1][1],dp[n - 1][2]);
    }
};

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

2.1.题目来源

本题还是来自于力扣,下面小编给出具体题目的链接:714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)

2.2.题目分析

下面就到了喜闻乐见的题目分析环节,本题其实和第一个题高度相似,只不过本题比第一个题要少了冷却期,多了手续费环节,所以此时我们在用状态机分析股票的时候,我们无须在分析三个状态,仅需两个状态我们就可以把这个题目做出来,只不过此时我们在每一次交易完成的时候都需要付手续费,这是和第一个题不同的地方,但是整体来说,本题的难度其实已经算是下降了,下面小编讲述一下本题的理论讲解。

2.3.思路讲解

首先,本题可以通过设置一个二维的dp表或者建立两个一维的dp表来实现本题的思路分析,这里我选用的是两个一维的dp表来实现的,分别叫f表和g表,那么接下来我们就可以按照动态规划五步走来实现本题目的思路讲解。

1.状态表示

此时我们通过题目的定义来对两个表进行正确的状态表示,此时我们可以清晰的知道本题一共就两个状态,分别是买入状态和卖出状态,所以小编此时便对两个表根据之和两个状态进行了定义。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
f[i]; //到达i位置的时候,处于买入状态,此时的最大利润。
g[i]; //到达i位置的时候,处于卖出状态,此时的最大理论
2.状态转换方程

此时我们就可以通过状态表示来写出状态转换方程了,不过由于本题的复杂度蛮高的,所以小编还是推荐各位使用状态机来正确表示出状态转换方程,因为状态机可以极大程度上减少我们出错的概率。其状态如下图所示:

如果此时我们当天是买入状态,那么它的前一天可能还是买入状态,或者前一天是卖出状态,通过买股票进入了买入状态。

如果当天是卖出状态,那么前一天可能还是卖出状态,或者前一天是买入状态,只不过此时卖出了股票进入了卖出状态,此时我们有一个值得注意的点,那就是此时我们已经涉及到了手续费问题,因为已经完成了一笔交易,所以我们在得到卖股票的钱的时候,记得把手续费也交一下。

此时我们就完整的写出一个状态机,下面我们就可以根据状态机写出状态转移方程了,此时我们需要取到每一个状态的最大值,因为此时我们要得到最大理论。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
f[i] = max(f[i - 1],g[i - 1] - prices[i]);
g[i] = max(g[i - 1],f[i - 1] + prices[i] - fee);
3.初始化

本题的越界问题还是很好发现的,此时当我们是第一个元素的时候,我们无法知道上一个元素的状态,因为上一个元素已经是越界状态了,我们可以根据每一个表的定义,来对第一个位置进行初始化,由于f表代表买入,所以第一个位置的元素肯定是买入了,而g表表示的卖出,因为第一个位置的元素没法卖掉,所以此时我们的g[0]就是0。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
f[0] = -pirce[0]; 
g[0] = 0;
4.填表顺序

从左到右依次填写即可。

5.返回值

按理说此时我们返回两个表最后一个位置最大元素即可,但是此时我们通过定义就可以知道此时的f表代表着买入,g表代表着卖出,买入和卖出,仔细一想便可以知道当我们手里没股票的时候,证明此时我们的理论已经是最高了,所以我们仅需返回g表最后一个位置的元素即可。

2.4.代码书写

首先,我们先要创建好两个dp表,它们的大小跟着给定数组的大小一致即可,然后把相应位置的元素进行初始化。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int n = prices.size();
vector<int> f(n); //这个状态表示买入状态,此时手上有股票
vector<int> g(n);  //这个表示卖出状态,此时手上没股票
f[0] = -prices[0];

创建完表后,我们就可以根据之前我们分析的状态转换方程来填表了,此时我们借助循环就可以做到,填完表后,我们返回g表最后一个位置的元素即可。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
for(int i = 1 ; i < n ; i++)
{
    f[i] = max(f[i - 1],g[i - 1] - prices[i]);
    g[i] = max(g[i - 1],f[i - 1] + prices[i] - fee);
}
return g[n - 1];
2.5.代码展示
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> f(n); //这个状态表示买入状态,此时手上有股票
        vector<int> g(n);  //这个表示卖出状态,此时受伤没股票
        f[0] = -prices[0];
        for(int i = 1 ; i < n ; i++)
        {
            f[i] = max(f[i - 1],g[i - 1] - prices[i]);
            g[i] = max(g[i - 1],f[i - 1] + prices[i] - fee);
        }
        return g[n - 1];
    }
};

3.总结

本文到这里也就结束了,这是小编第一次讲述股票问题,所以内容有问题的话私信我即可,直接在评论区给我指点一下也没有问题,小编在写本文章的时候,已经度过了艰难的期末周,所以我现在十分舒畅,我准备在这几天多产出几篇文章以备不时之需,一起写题的时光总是很短暂的,那么各位大佬们,我们下一篇文章见啦。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-04-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
git安装教程和git命令使用详解
原文出处:涂根华的博客 一:Git是什么? Git是目前世界上最先进的分布式版本控制系统。 二:SVN与Git的最主要的区别? SVN是集中式版本控制系统,版本库是集中放在中央服务器的,而干活的时候,用的都是自己的电脑,所以首先要从中央服务器哪里得到最新的版本,然后干活, 干完后,需要把自己做完的活推送到中央服务器。集中式版本控制系统是必须联网才能工作,如果在局域网还可以,带宽够大,速度够快,如果在互联网下,如果网 速慢的话,就纳闷了。 Git是分布式版本控制系统,那么它就没有中央服务器的,每个人的电脑就是
挑战者
2018/06/29
8710
超详细的 Git 实战教程,傻瓜一看也会!
作者:涂根华 来自:cnblogs.com/tugenhua0707/p/4050072.html
Java技术栈
2019/07/08
1.4K0
超详细的 Git 实战教程,傻瓜一看也会!
Git使用教程:最详细、最傻瓜、最浅显、真正手把手教!
导读:因为教程详细,所以行文有些长,新手边看边操作效果出乎你的预料。GitHub虽然有些许改版,但并无大碍。
Java团长
2018/10/18
35K1
Git使用教程:最详细、最傻瓜、最浅显、真正手把手教!
Git 从入门到放不下
https://github.com/gafish/gafish.github.com
良月柒
2019/09/26
2.3K0
Git 从入门到放不下
Git使用教程(看完会了也懂了)
默认打开的地址是应该是用户目录,也就是c盘Users下某个地方,下面就先在固定的地址新建一个空的目录作为我们的新项目,叫做FastApiProject:
MinChess
2023/08/13
1.6K0
Git使用教程(看完会了也懂了)
想要学Git,这一篇就够了
现在是资源共享的时代,同样也是知识分享的时代,如果你觉得本文能学到知识,请把知识与别人分享。
互扯程序
2018/07/30
4850
想要学Git,这一篇就够了
Git学习总结
git 是分布式的,所以其核心就是分支,分支的意义在于,可以将项目代码按照功能、模块拆分成不同的分支。比如这个产品要加一个支付功能和一个登陆功能,可以创建两个分支,交给不同的开发人员并行开发。登陆功能先开发完,测试无误后合并改分支到 master 分支,master 分支部署上线。支付功能虽然没有开发完成,但是在另一条分支上,所以产品上线和功能开发完全不受影响。这才是分布式开发的高效模式。 在 git 中,工作目录下面的所有文件都不外乎这两种状态:已跟踪或未跟踪。已跟踪的文件是指本来就被纳入版本控制管理的文件,在上次快照中有它们的记录,工作一段时间后,它们的状态可能是未更新,已修改或者已放入暂存区。而所有其他文件都属于未跟踪文件。它们既没有上次更新时的快照,也不在当前的暂存区域。初次克隆某个仓库时,工作目录中的所有文件都属于已跟踪文件,且状态为未修改。
零式的天空
2022/03/22
4820
Git常用命令汇总篇(附使用详细介绍)
众所周知,Git是一个开源的分布式版本控制系统,用于跟踪和管理源代码的变更。而Git有着大量的常用命令。
Masutaa大师
2023/08/09
5600
Git常用命令汇总篇(附使用详细介绍)
大话Git
Git是什么 Git是一个分布式版本控制系统。它可以很方便的记录你的每一次变动,而不需要每次都备份,还能让你和他人很方便的协同开发。这样你每次做了什么改动,瞄一眼就一清二楚了。 -- 安装Git 从官
洗尽了浮华
2018/01/22
8210
大话Git
Git使用教程:最详细、最傻瓜、最浅显、真正手把手教!
因为教程详细,所以行文有些长,新手边看边操作效果出乎你的预料。GitHub虽然有些许改版,但并无大碍。
龙哥
2020/07/10
7430
Git使用教程:最详细、最傻瓜、最浅显、真正手把手教!
让Git不再难学
在团队做过软件开发的,版本控制必是不可或缺的一项。目前,版本控制主要分为集中式版本控制系统和分布式版本控制系统 ,即大家熟知的SVN和Git。Git是当下最流行的分布式版本控制系统,故,今天,我们就来研究一下Git的神奇之处。
Jacklin999
2018/09/12
8840
让Git不再难学
Git上手实用一文通
2.进入demo目录下:git init命令将这个目录变成git可以管理的仓库(repository)。将仓库建好后,仓库目录下会多了一个.git隐藏文件夹。可以用ls -ah查看隐藏文件。
用户7353950
2022/06/23
4270
Git上手实用一文通
Git工具使用教程,简单易懂
假设文件原已commit,目前情况是——已经在目录下手动或$ rm <file-name>删除文件
Alone88
2019/10/22
1.1K0
相关推荐
git安装教程和git命令使用详解
更多 >
LV.0
这个人很懒,什么都没有留下~
目录
  • 1.买卖股票的最佳时机含冷却期
    • 1.1.题目来源
    • 1.2.题目分析
    • 1.3.思路讲解
      • 1.状态表示
      • 1.2.状态转换方程
      • 3.初始化
      • 4.填表顺序
      • 5.返回值
    • 1.4.代码实操
    • 1.5.代码展示
  • 2.买卖股票的最佳时机含手续费
    • 2.1.题目来源
    • 2.2.题目分析
    • 2.3.思路讲解
      • 1.状态表示
      • 2.状态转换方程
      • 3.初始化
      • 4.填表顺序
      • 5.返回值
    • 2.4.代码书写
    • 2.5.代码展示
  • 3.总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档