Java通过动态规划设计股票买卖最佳时机

目录
  • 买卖股票的最佳时机
  • 动态规划

买卖股票的最佳时机

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

示例:

链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock

动态规划

因为对每一天只有两个状态,买入股票和卖出股票,因此定义 dp[][2]

1. dp[i][2] 数组表示的含义 :

dp[i][0] 表示第 i 天买入股票能获得的最大利润,dp[i][1] 表示第一天卖出股票能获得的最大利润

2. 状态转移方程:

dp[i][0] = max(dp[i-1][0], -prices[i])

解释: 第 i 天对买入股票状态,只有两种操作,买入股票或者不买股票。因此,第 i 天能获得的最大利润为 第 i 天不买股票(dp[i-1][0]) 和 第 i 天买入股票(-prices[i]) 的利润的最大值。

dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

解释: 第 i 天对卖出股票,只有两种操作,卖出股票或者不卖出股票。因此,第 i 天能获得的最大利润为 第 i 天卖出股票 (dp[i-1][0] + prices[i])和 第 i 天不卖出股票 的利润的最大值 (dp[i-1][1]

3. 初始化

第 0 天买入,得到的利润为 -price[0]

第 0 天卖出,得到的利润为 0

dp[0][0] = -price[0]
dp[0][1] = 0

代码:

    // 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        // dp 表示当天能获得的最大利润
        int[][] dp = new int[prices.length][2]; // 对每一天来说,就两个状态,一个是买入,一个是卖出
        dp[0][0] = -prices[0]; // 第一天买入
        dp[0][1] = 0; // 第一天卖出
        for(int i=1; i<prices.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }
        return dp[prices.length-1][1];
    }

变式一: 可以重复买入,卖出

   // 买卖股票的最佳时机2 —— 可以多次买入和卖出,但是注意每次只能持有一张股票,就是必须是 买 - 卖 - 买 - 卖 - 买 - 卖 ....这种顺序
    public int maxProfit2(int[] prices) {
        // 本题与上题的区别就在于状态转移方程不同 -- 本题可以用之前得到的利润 (即 dp[i-1][1],上一轮卖出后剩下的钱) 再去买入,而上一题必须 0-price[i] 买入
        // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]); ---- 买入股票能得到的最大利润状态转移方程有变化
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i=1; i<prices.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]); // 当天可能执行股票买入
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]); // 当他可能执行股票卖出
        }
        return dp[prices.length-1][1];
    }

变式二:可以执行买入卖出操作两次

   // 买卖股票的最佳时机3 —— 本题与上一题的区别在于,本题只能执行两次买入、卖出操作
    public int maxProfit3(int[] prices) {
        // 每次可执行的操作状态为 ,第一次买入、第一次卖出、第二次买入、第二次卖出,因此 dp 定义为
        int[][] dp = new int[prices.length][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for(int i=1; i<prices.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
            dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i]);
            dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i]);
        }
        return dp[prices.length-1][3];
    }

变式三:可以执行买卖操作 K 次

    // 买卖股票的最佳时期 —— 最多进行 K 次交易
    public int maxProfit(int k, int[] prices) {
        // 就是两次交易的升级版
        int[][] dp = new int[prices.length][2*k+1]; // 奇数表示买入,偶数表示卖出
        // 初始化
        for(int j=1; j<2*k; j+=2){
            dp[0][j] = -prices[0];
        }
        for(int i=1; i<prices.length; i++){
            for(int j=0; j<2*k-1; j+=2){
                dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] - prices[i]);
                dp[i][j+2] = Math.max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]);
            }
        }
        return dp[prices.length-1][2*k];
    }

变式四:含冷冻期

   // 买卖股票含冷冻期
    public int maxProfit(int[] prices) {
        // 一共四种状态 买入 卖出(早就卖出保存卖出态,当天卖出) 冷冻
        int dp[][] = new int[prices.length][4];
        // 初始化
        dp[0][0] = -prices[0];
        for(int i=1; i<prices.length; i++){
            // 买入状态 —— 前一天就是买入状态 + 前一天是卖出状态今天买入了 + 前一天是冷冻状态今天买入了
            dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][3]-prices[i], dp[i-1][2]-prices[i]) );
            // 卖出态1 —— 前一天就是卖出态1 + 前一天是冷冻态
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]);
            // 卖出态2 —— 当天卖出了
            dp[i][2] = dp[i-1][0] + prices[i];
            // 冷冻态 —— 前一天是卖出态2
            dp[i][3] = dp[i-1][2];
        }
        return Math.max(dp[prices.length-1][1], Math.max(dp[prices.length-1][2], dp[prices.length-1][3]));
    }

变式五:含手续费

    // 买卖股票的最佳时机,含手续费
    public int maxProfit2(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        // 初始化
        dp[0][0] = -prices[0] - fee;
        for(int i=1; i<prices.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i] - fee);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }
        return dp[prices.length-1][1];
    }

到此这篇关于Java通过动态规划设计股票买卖最佳时机的文章就介绍到这了,更多相关Java股票买卖内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java背包问题动态规划算法分析

    背包问题 [题目描述] 一个旅行者有一个最多能装 MM 公斤的背包,现在有 nn 件物品,它们的重量分别是W1,W2,-,WnW1,W2,-,Wn,它们的价值分别为C1,C2,-,CnC1,C2,-,Cn,求旅行者能获得最大总价值. [输入] 第一行:两个整数,MM(背包容量,M<=200M<=200)和NN(物品数量,N<=30N<=30): 第2-N+12-N+1行:每行二个整数Wi,CiWi,Ci,表示每个物品的重量和价值. [输出] 仅一行,一个数,表示最大总价值. [输入

  • Java动态规划之硬币找零问题实现示例

    目录 问题描述: 问题分析: 具体的过程如下: 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法.20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的

  • Java实现动态规划背包问题

    目录 前言 一.原理 1.1 最优子结构性质 1.2 递归关系 二.算法描述 2.1 算法描述 2.2 图解 2.3 构造最优解 三. 0 − 1 0-1 0−1 背包问题相关题目 3.1 题目 3.2 源程序(Java求解 0 − 1 0-1 0−1背包问题) 3.3 运行结果 总结 前言 给定 n n n 种物品和一个背包.物品 i i i 的重量是 w i wi wi,其价值为 v i vi vi,背包的容量为 c c c.问应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 一.

  • Java使用动态规划算法思想解决背包问题

    目录 动态规划算法 动态规划算法的思想 最优性原理 动态规划算法的三大特点 动态规划算法中的0/1背包问题 动态规划算法的优点 小结 动态规划算法 动态规划算法的思想 动态规划算法处理的对象是多阶段复杂决策问题,动态规划算法和分治算法类似,其基本思想也是将待求解问题分解成若干个子问题(阶段),然后分别求解各个子问题(阶段),最后将子问题的解组合起来得到原问题的解,但是与分治算法不同的是,子问题往往不是相互独立的,而是相互联系又相互区别的 动态规划算法问题求解的目标是获取导致问题最优解的最优决策序

  • Java动态规划之丑数问题实例讲解

    问题描述: 我们把只包含质因子 2.3 和 5 的数称作丑数(Ugly Number).求按从小到大的顺序的第 n 个丑数. 注: 1也是丑数 思路: 我们来分析一下丑数如何得到,肯定是由前面的丑数乘2,乘3或者乘5得到,因此这是一道动态规划题. 使用 dp[i] 记录第i个丑数, 初始值dp[0] = 1,返回 dp[n-1] 使用 a,b,c 记录以及 2,3,5 分别乘到了第几个丑数 动态规划方程为: dp[i] = Math.min(Math.min(dp[a]*2, dp[b]*3),

  • Java通过动态规划设计股票买卖最佳时机

    目录 买卖股票的最佳时机 动态规划 买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格.你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票.设计一个算法来计算你所能获取的最大利润.返回你可以从这笔交易中获取的最大利润.如果你不能获取任何利润,返回 0 . 示例: 链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock 动态规划

  • 老生常谈Java异常处理和设计(推荐)

    在程序设计中,进行异常处理是非常关键和重要的一部分.一个程序的异常处理框架的好坏直接影响到整个项目的代码质量以及后期维护成本和难度.试想一下,如果一个项目从头到尾没有考虑过异常处理,当程序出错从哪里寻找出错的根源?但是如果一个项目异常处理设计地过多,又会严重影响到代码质量以及程序的性能.因此,如何高效简洁地设计异常处理是一门艺术,本文下面先讲述Java异常机制最基础的知识,然后给出在进行Java异常处理设计时的几个建议. 若有不正之处,请多多谅解和指正,不胜感激. 以下是本文的目录大纲: 一.什

  • Java 23种设计模型详解

    设计模式(Design Patterns)                                   --可复用面向对象软件的基础 设计模式(Design pattern)是一套被反复使用.多数人知晓的.经过分类编目的.代码设计经验的总结.使用设计模式是为了可重用代码.让代码更容易被他人理解.保证代码可靠性. 毫无疑问,设计模式于己于他人于系统都是多赢的,设计模式使代码编制真正工程化,设计模式是软件工程的基石,如同大厦的一块块砖石一样.项目中合理的运用设计模式可以完美的解决很多问题,每

  • java基于ConcurrentHashMap设计细粒度实现代码

    细粒度锁: java中的几种锁:synchronized,ReentrantLock,ReentrantReadWriteLock已基本可以满足编程需求,但其粒度都太大,同一时刻只有一个线程能进入同步块,这对于某些高并发的场景并不适用.比如银行客户a向b转账,c向d转账,假如这两个线程并发,代码其实不需要同步.但是同时有线程3,e向b转账,那么对b而言必须加入同步.这时需要考虑锁的粒度问题,即细粒度锁. 网上搜寻了一些关于java细粒度锁的介绍文章,大部分是提供思路,比如乐观锁,String.i

  • 基于java计算买卖股票的最佳时机

    这篇文章主要介绍了基于java计算买卖股票的最佳时机,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 问题: 可以将问题转化为如下图所示,即求多个累计的收入差 分析: 如果当前位置i的价格比i+1的价格高,则当前不是买入点,则继续判断下一个位置, 如果当前位置i的价格比i+1的价格低,并且i+1仍比i+1+1低,则在当前位置买入,知道i+n比i+n+1大时,卖出. 继续下一轮判断 package com.example.demo; public

  • Java实现计算器设计

    本文实例为大家分享了Java实现计算器设计的具体代码,供大家参考,具体内容如下 需求分析 目的是实现一个基于Java的可以求解带括号加减乘除表达式的带界面的计算器. 需要知道的Java技术:Java Swing(Java图形界面设计).Java集合(栈).lambda表达式.Java基础等. 设计思路 1.实现一个Java计算器界面类 2.实现一个Java计算带括号加减乘除表达式的类 3.实现主函数调用 设计实现 Java计算器项目结构: Calculator类为计算器界面设计.Calculat

  • 理解Java面向对象编程设计

    目录 1 前言 2 结构化程序设计 3 面向对象编程设计 4 码农洞见 4.1 两种编程范式之间的区别 4.2 两种编程范式之间的联系 1 前言 计算机革命的起源来自机器.编程语言就像是那台机器.它不仅是我们思维放大的工具与另一种表达媒介,更像是我们思想的一部分.语言的灵感来自其他形式的表达,如写作,绘画,雕塑,动画和电影制作.编程语言就是创建应用程序的思想结构. 面向对象编程(Object-Oriented Programming OOP)是一种编程思维方式和编码架构. 2 结构化程序设计 结

  • Java+MySQL实现设计优惠券系统

    目录 1 Scenario 场景 2 Service 服务 2.1 服务结构设计 2.2 优惠券系统难点 3 Storage存储 3.1 表单设计 券批次(券模板),coupon_batch 券 规则 3.2 优惠券系统 触达系统 系统用户数增加到万级 发一封站内信的步骤 千w级用户数 用户侧操作 系统侧操作 领券 用券 返回可用券 选择可用券,并返回结果 表设计 Scale扩展 通知信息表(notify_msg)设计 数据库层面优化 - 索引 发券接口,限流保护 1 Scenario 场景 电

随机推荐