首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >前端用动态规划玩股票 - 最终章

前端用动态规划玩股票 - 最终章

作者头像
LamHo
发布于 2022-09-26 02:44:44
发布于 2022-09-26 02:44:44
28000
代码可运行
举报
文章被收录于专栏:小前端看世界小前端看世界
运行总次数:0
代码可运行

这篇文章和你去买股票没有半毛钱关系,既然你进来了,就来看看前端算法呗,嘿嘿嘿嘿!

前端没有需要刷算法?

为什么需要做算法题?大家其实都有发现在这一段2020年开始,各大公司对于前端的面试中,都不同程度的加入了算法题的测试,其中让大家最有感悟的就是字节跳动的前端面试,加入了大量的算法考验,其中不乏有很多在LeetCode上的中等以及困难题目,我也在知乎上发起了一个提问。浏览量上百万,也得到了很多的评论。

为什么字节跳动的前端面试需要那么难的算法题?

经过看了很多的评论,也明白了前端刷算法题的重要性,经过一段时间刷LeetCode,让我深有的体会的并不是这些算法在前端领域当中是否真的用到,而是算法能提高自身对于问题的理解能力,以及解决问题的能力,在刷了100多题之后,重新的自己的审视,发现自己对于同样问题的思考方式有一定的改变,所以暂且得出的结论是,刷算法对于前端开发来说,主要是提升自己的思考能力,以及对问题的分析能力

本文概括

本文主要是讲述在LeetCode当中的股票类型题目使用动态规划的方式去解题的思路以及如何解题。

如果您已经做过,并深入理解,请阅读我的文章,看看我是否理解正确,如果你并没有做过该类题目,那么也可以阅读本文,先理解,然后关闭页面,打开LeetCode,尝试一下,挑战一下自己。


本篇文章是前端用动态规划玩股票的最终章,这次我们来挑战一下LeetCode中股票题目中的困难两题:

如果你并没有看过之前的两篇文章,建议先仔细阅读再看最终章。

Lam:前端用动态规划玩股票Lam:前端用动态规划玩股票II

买卖股票的组价时机III

分析:

这一题中,是基于第二题《买卖股票的最佳时机2》的基础上,加上了购买次数的限制。本题中限制了最多只能购买2次的限制,但是并非必须购买2次。所以我们可以想到第二次购买必须是第一次非持有股票的利润 - 今日股价来决定是否买入的。

解题:

因为这里涉及到了限制2次购买,所以一共有4个状态

  • 第一次 非持股
  • 第一次 持股
  • 第二次 非持股
  • 第二次 持股

在这里我们可以回顾一下第一题《买卖股票的最佳时机》时候我们的状态转移方程,因为只限制1次购买,与这里第一次持股的条件一样,并不存在累加利润的情况,只需要找到比当前持股成本更低和非持股的利润更高的状态即可,所以这里第一次买卖的状态转移方程就得出了。

  • 第一次 不持股利润 = max(第一次昨天不持股利润, 第一次昨天持股利润 + 今天价格)
  • 第一次 持股利润 = max(第一次昨天持股利润, 今天价格)

那么第二次买卖的状态转移方程怎么写呢?

首先我们要清楚,第二次购买肯定是在第一次购买后,所以第二次的持股条件应该是基于第一次非持股时的利润进行计算,所以得出第二次购买的状态转移方程。

  • 第二次 不持股利润 = max(第二次昨天不持股利润, 第二次昨天持股利润 + 今天价格)
  • 第二次 持股利润 = max(第二次昨天持股利润, 第一次不持股利润 - 今天价格)

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
var maxProfit = function ( prices ) {

    if ( prices.length <= 1 ) return 0;
    if ( prices.length == 2 ) return Math.max( 0, prices[1] - prices[0] );

    const N = prices.length;

    // 第一次交易
    let dp_0_0 = 0; // 卖出后的利润
    let dp_0_1 = -prices[0]; // 买入后的利润

    // 第二次交易
    let dp_1_0 = 0; // 卖出后的利润
    let dp_1_1 = -prices[0]; // 买入后的利润

    for ( let i = 1; i < N; i++ ) {
        // 第二次卖出 根据当前买入后的利润 + 今日金额
        dp_1_0 = Math.max( dp_1_0, dp_1_1 + prices[i] );
        // 第二次买入,当前买入后的利润 是否大于 第一次买入后的利润 - 今日金额
        dp_1_1 = Math.max( dp_1_1, dp_0_0 - prices[i] );

        // 第一次买出,卖出条件是当前买入后利润+今日金额 是否大于 当前卖出的总利润
        dp_0_0 = Math.max( dp_0_0, dp_0_1 + prices[i] );
        // 都一次买入,判断是否有更低的买入价
        dp_0_1 = Math.max( dp_0_1, -prices[i] );
        
    }

    return dp_1_0;
}

买卖股票的组价时机IV

分析:

最后一题和上一题其实是一样,只是将限制购买2次变为n次。

解题:

所以状态转移方程是和上一题一样的,但是有一些不一样,就是需要区分是否为第一次买卖。

  • 第一次 不持股利润 = max(第一次昨天不持股利润, 第一次昨天持股利润 + 今天价格)
  • 第一次 持股利润 = max(第一次昨天持股利润, 今天价格)
  • 第n次 不持股利润 = max(第n次昨天不持股利润, 第n次昨天持股利润 + 今天价格)
  • 第n次 持股利润 = max(第n次昨天持股利润, 第n-1次不持股利润 - 今天价格)

在编写代码的时候就需要留意了,在这一题中,我们就不能去维了,因为购买的次数的n次,所以我们就需要dp数组来记录每一次的买卖记录了。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
var maxProfit = function(k, prices) {

    const N = prices.length;

    if (N <= 1 || k < 1) return 0;


    // 当限定的购买天数大于可购买天数的一半,可以视为没有任何限制
    if ( k > N / 2 ) {

        let dp_i_0 = 0;
        let dp_i_1 = -prices[0];

        for ( let i = 1; i < N; i++ ) {
            const temp = dp_i_0;
            dp_i_0 = Math.max( dp_i_0, dp_i_1 + prices[i] );
            dp_i_1 = Math.max( dp_i_1, temp - prices[i] );
        }

        return dp_i_0;
    }


    // 不确定传入的限制次数是多少,所以不能进行降维处理
    // 构建dp;
    const dp = [];
    for ( let i = 0; i < N; i++ ) {
        
        dp[i] = [];

        for ( let n = 0; n < k; n++ ) {
            if ( i == 0 ) {
                dp[i][n] = [0, -prices[0]]
            } else {
                dp[i][n] = [0,0];
            }
        }

    }
    
    // 循环天数
    for ( let i = 1; i < N; i++ ) {
        // 循环限制购买次数,倒序
        for ( let n = k - 1; n >= 0; n-- ) {
            // 需要区分第一次买卖还是非第一次买卖
            dp[i][n][0] = Math.max( dp[i-1][n][0], dp[i-1][n][1] + prices[i] );
            dp[i][n][1] = Math.max( dp[i-1][n][1], n == 0 ? -prices[i] : dp[i-1][n-1][0] - prices[i] );

        }

    }

    return dp[N-1][k-1][0];
};

总结

以上就是所有股票的题目解法,其实只要知道第一第二题的状态转移方程,其实就比较好得出后面的其他买卖条件下的状态转移方程了。

经过这几题股票题目,可以大概了解到动态规划的大概是使用方式,动态规划在很多大厂都有不少的面试题,主要是因为动态规划考验的并非具体的算法如何编写,而是背后的对问题的分析能力,以及如何将问题分解成小问题最终得出状态转移方程。

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

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

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
前端用动态规划玩股票
为什么需要做算法题?大家其实都有发现在这一段2020年开始,各大公司对于前端的面试中,都不同程度的加入了算法题的测试,其中让大家最有感悟的就是字节跳动的前端面试,加入了大量的算法考验,其中不乏有很多在LeetCode上的中等以及困难题目,我也在知乎上发起了一个提问。浏览量上百万,也得到了很多的评论。
LamHo
2022/09/26
4420
前端用动态规划玩股票
前端用动态规划玩股票II
为什么需要做算法题?大家其实都有发现在这一段2020年开始,各大公司对于前端的面试中,都不同程度的加入了算法题的测试,其中让大家最有感悟的就是字节跳动的前端面试,加入了大量的算法考验,其中不乏有很多在LeetCode上的中等以及困难题目,我也在知乎上发起了一个提问。浏览量上百万,也得到了很多的评论。
LamHo
2022/09/26
2850
前端用动态规划玩股票II
聊聊买卖股票的最佳时机
最近梳理高频动态规划问题,股票问题当然是非常经典的动态规划问题,并且整个系列有好几道题,这里我整理了6道股票系列的经典问题分享给大家,咱们今天聊聊买卖股票的最佳时机。
bigsai
2022/04/08
5550
聊聊买卖股票的最佳时机
九十二、动态规划系列之股票问题(上)
股票买卖这一类的问题,都是给一个输入数组,里面的每个元素表示的是每天的股价,并且你只能持有一支股票(也就是你必须在再次购买前出售掉之前的股票),一般来说有下面几种问法:
润森
2022/08/17
4970
浅谈什么是动态规划以及相关的「股票」算法题
动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。在学习动态规划之前需要明确掌握几个重要概念。
五分钟学算法
2019/05/15
1.2K0
详解股票买卖算法的最优解(一)
主要用的技巧是“状态机”,那么什么是“状态机”呢?没听过的小伙伴会觉得它很高大尚,但今天我们讨论过后,你会发现其实它就是那么回事。
HUC思梦
2020/09/10
1.3K0
LeetCode股票交易类算法题目总结(一次交易,两次交易,无数次交易)
大家好,我是千与千寻,前一段时间的基金市场波动很大啊,也就又诞生了很多“韭菜”,在这里千寻也提醒大家“股市有风险,入市需谨慎”,玩基金一定用不着急用的钱哦~
千与编程
2023/04/28
5860
LeetCode股票交易类算法题目总结(一次交易,两次交易,无数次交易)
【前端算法】买卖股票的最佳时机含手续费—— 贪心算法、动态规划实现
给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。
徐小夕
2022/02/09
3550
【动态规划】【简单多状态dp问题】买卖股票相关问题(冷冻期、手续费、限制次数)
一维表示第 i 天;二维表示交易次数(可加一维表示买入还是卖出,不过我们可以直接用两个表)
椰椰椰耶
2024/11/15
1570
【动态规划】【简单多状态dp问题】买卖股票相关问题(冷冻期、手续费、限制次数)
LeetCode买卖股票之一:基本套路(122)
欢迎访问我的GitHub 这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demos 关于《LeetCode买卖股票》系列 在LeetCode上,有数道和买卖股票有关的题目,覆盖了简单、中等、困难,要求都是选择低价时间买入、高价时间卖出,以求达到利润最大化 这类题型的特点就是:典型的动态规划题型,掌握套路后,越做越开心,就算难度是困难的题目,也能从容面对 于是,欣宸将此类题目聚集在一起,集中火力分析和解题,构成了《LeetCode买卖股票》
程序员欣宸
2022/09/26
3140
dp 动态规划有限状态机
动态规划虽然说有一定难度,主要是找到状态转移的公式,但是也依然是有些规律可以找寻的。
Tim在路上
2020/08/04
1.4K0
搞定大厂算法面试之leetcode精讲3.动态规划
动态规划,英文:Dynamic Programming,简称DP,将问题分解为互相重叠的子问题,通过反复求解子问题来解决原问题就是动态规划,如果某一问题有很多重叠子问题,使用动态规划来解是比较有效的。
全栈潇晨
2021/11/22
4360
搞定大厂算法面试之leetcode精讲3.动态规划
Leetcode No.123 买卖股票的最佳时机 III(动态规划)
示例 1: 输入:prices = [3,3,5,0,0,3,1,4] 输出:6 解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。 随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。
week
2021/11/29
2760
Leetcode No.123 买卖股票的最佳时机 III(动态规划)
数据结构与算法 | 动态规划算法(Dynamic Programming)
上一篇文末已经提到了记忆化搜索是动态规划(Dynamic Programming)的一种形式,是一种自顶向下(Top-Down)的思考方式,通常采用递归的编码形式;既然动态规划有自顶向下(Top-Down)的递归形式,自然想到对应的另外一种思考方式自底向上( Bottom-Up ),也就是本篇要写的内容。
Java研究者
2023/11/16
5570
数据结构与算法 | 动态规划算法(Dynamic Programming)
LeetCode 股票问题,秒杀!
此文为转载翻译,和原文相比,这篇文章多了未优化空间的代码,且代码都重新写了,另外更改了部分文字描述。
五分钟学算法
2024/03/05
1940
LeetCode 股票问题,秒杀!
力扣309——最佳买卖股票时机含冷冻期
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
健程之道
2020/02/13
4120
​LeetCode刷题实战309:最佳买卖股票时机含冷冻期
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2021/07/06
3300
LeetCode-309-最佳买卖股票时机含冷冻期
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
benym
2022/07/14
2170
Leetcode | 第一节:动态规划(上)
从去年7月到现在,我已经在北京的互联网公司呆了整整一年的时间。这中间经历过各种各样的酸甜苦辣,自己为了面试刷题的过程(从杉数到滴滴——未入门算法工程师再找实习工作记),也会经常听到北美同学面试的时候所遇到的各种艰难。是的,只要是互联网公司,无论是国内还是国外,总是要考察很多leetcode的东西。而leetcode如何刷,刷多少,刷到什么程度,其实各个公司也各不相同。但是事实上,leetcode的本质考察点是算法与数据结构,而除去基本的算法与数据结构外,leetcode困难的地方在于熟练度+一些技巧。然而技巧毕竟是存量,不是增量,我们刷多了,自然就有经验。所以这一个系列,我们不面向easy的题目,而更多关注hard和medium+的高频题,并通过大量的leetcode原题,来刻画出互联网公司究竟会考察哪些实际算法与数据结构的知识,以达到复习《算法与数据结构》的效果。
学弱猹
2021/08/10
7000
Leetcode | 第一节:动态规划(上)
☆打卡算法☆LeetCode 123. 买卖股票的最佳时机 III 算法解析
链接: 123. 买卖股票的最佳时机 III - 力扣(LeetCode) (leetcode-cn.com)
恬静的小魔龙
2022/08/07
3660
☆打卡算法☆LeetCode 123. 买卖股票的最佳时机 III 算法解析
推荐阅读
相关推荐
前端用动态规划玩股票
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验