动态规划-求买卖股票所能获得的最大收益(hard)

2024-06-03 19:36

本文主要是介绍动态规划-求买卖股票所能获得的最大收益(hard),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、问题描述

二、解题思路

1.先看有哪几个可变参数:

        (1).当前第几天 nowday(范围:0->n-1)

        (2).剩余交易次数 restTime(范围:k->0)

        (3).当天可买入还是可卖出 isnowHold(0 表示当前未持有可买入,1 表示当前持有可卖出)

2.需要三维dp数组来实现动态规划过程

        dp数组=[n][k+1][2]        n 表示天数维度        k+1表示剩余交易次数维度        2表示当天可买入还是卖出状态维度。

        price数组表示每一天的股票价格。

        (1).dp数组初始化(这一步很重要):当天数为第一天时,可买入,无论交易次数剩(0~k-1)次,买入以后盈利值均为负数(负的第一天的股票价格):

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

        状态转移方程的推导过程如下:

        (2).要使第nowday天股票状态是未持有 (isnowHold=0) ,如果前一天未持有则直接迁移过来,如果前一天持有股票时的状态则需要卖出

        比较两种方式的盈利值取最大值作为当前未持有时的状态 dp[nowday][restTime][0]

        状态转移公式:

        dp[i][j][0]=Max(dp[i-1][j][0],dp[i-1][j][1]+price[i])

        (3).要使第nowday天股票状态是持有 (isnowHold=1) ,如果前一天持有则直接迁移,如果前一天没有,则需要买入

        比较两种方式的盈利值取最大值作为当前持有时的状态 dp[nowday][restTime][1]       

        状态转移公式: 

        dp[i][j][1]=Max(dp[i-1][j][1],dp[i-1][j+1][0]-price[i])

三、代码实现

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param prices int整型一维数组 * @param k int整型 * @return int整型*/public int maxProfit (int[] prices, int k) {// 使用动态规划解决此问题int nsize=prices.length;if(nsize==0){return 0;}//先看有哪几个可变参数://当前第几天 nowday(范围:0->n-1)//剩余交易次数 restTime(范围:k->0)//当天可买入还是可卖出 isnowHold(0表示未持有可买入,1表示持有可卖出)//初始化三维dp数组int[][][] dpArr=new int[nsize][k+1][2];for(int i=0;i<k;i++){//初始情况下第一天买入持有股票,盈利均为负值dpArr[0][i][1]=-prices[0];}//剩余k次的时候,盈利均为0;第1天就买入的情况上面已经初始化完成//所以下面外层天数循环从第二天开始,内层次数循环从k-1次开始for(int nowday=1;nowday<nsize;nowday++){for(int restTime=k-1;restTime>=0;restTime--){//要使第nowday天未持有股票,如果前一天未持有则直接迁移过来,如果前一天持有股票则需要卖出dpArr[nowday][restTime][0]=Math.max(dpArr[nowday-1][restTime][0],dpArr[nowday-1][restTime][1]+prices[nowday]);//要使第nowday天持有股票,如果前一天持有则直接迁移,如果前一天没有,则需要买入dpArr[nowday][restTime][1]=Math.max(dpArr[nowday-1][restTime][1],dpArr[nowday-1][restTime+1][0]-prices[nowday]);}}return dpArr[nsize-1][0][0];}
}

四、刷题链接

买卖股票的最好时机(四)_牛客题霸_牛客网

这篇关于动态规划-求买卖股票所能获得的最大收益(hard)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1027917

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta

poj 3422 有流量限制的最小费用流 反用求最大 + 拆点

题意: 给一个n*n(50 * 50) 的数字迷宫,从左上点开始走,走到右下点。 每次只能往右移一格,或者往下移一格。 每个格子,第一次到达时可以获得格子对应的数字作为奖励,再次到达则没有奖励。 问走k次这个迷宫,最大能获得多少奖励。 解析: 拆点,拿样例来说明: 3 2 1 2 3 0 2 1 1 4 2 3*3的数字迷宫,走两次最大能获得多少奖励。 将每个点拆成两个