金乡网站建设多少钱,张家口建设部网站,大连市城乡建设局网站,网页设计师 培训目录
一.买卖股票的最佳时机#xff1a;
二.买卖股票的最佳时机含冷冻期#xff1a;
三.买卖股票的最佳时期含⼿续费#xff1a;
四.买卖股票的最佳时机III:
五.买卖股票的最佳时机IV: 买卖股票的最佳时机问题介绍#xff1a;动态规划买卖股票的最佳时机是一个经典的…目录
一.买卖股票的最佳时机
二.买卖股票的最佳时机含冷冻期
三.买卖股票的最佳时期含⼿续费
四.买卖股票的最佳时机III:
五.买卖股票的最佳时机IV: 买卖股票的最佳时机问题介绍动态规划买卖股票的最佳时机是一个经典的算法问题。该问题的目标是在给定的股票价格数组中找到最大的利润即最佳的买入和卖出时间使得买入时间早于卖出时间。
下面我们通过一些例题来解决这一类动态规划的问题
一.买卖股票的最佳时机
题目链接121. 买卖股票的最佳时机 - 力扣LeetCode题目描述 给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 ①.动态规划解法 一.状态表示dp[ i ][ j ]下标为 i 这一天结束的时候手上持股状态为 j 时我们持有的最大利润。这里我们定义状态 j 两种情况分别为0 买入状态1 可交易状态二.状态转移方程dp[ i ][ 0 ] Math.max( dp[ i - 1 ][ 0 ], -prices[ i ]) ; ①.在前面一天已经是买入状态今天选择什么也不干今天结束后是买入状态。②.前面是可交易状态今天选择买入则今天结束后是买入状态这里注意不是dp[ i - 1][ 1 ] - prices[ i ];因为只能交易一次如果今天选择买入那后面一定要卖出这算一次交易),此时才可能有最大利润。则前面不能有交易利润为0.dp[ i ][ 1 ] Math.max( dp[ i - 1][ 1 ],dp[ i - 1][ 0 ] prices[ i ]);①.前面一天是可交易状态今天选择什么也不干今天结束后是可交易状态。②.前面一天是买入状态今天选择卖出今天结束后是可交易状态。三.初始化根据状态表示dp[ 0 ][ 0 ] - prices[ 0 ];第一天选择买入此时利润为 - prices[ 0 ]dp[ 0 ][ 1 ] 0;第一天选择什么也不干或则交易一次此时的利润为0;四.填表顺序根据状态转移方程从左往右从上往下填写.五.返回值dp[ n - 1 ][ 1 ];n为prices数组的长度,最后一天结束后是可交易状态此时为最大利润. 各个状态关系图 代码详解 class Solution {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值public int maxProfit(int[] prices) {int n prices.length;int[][] dp new int[n][2];//初始化dp[0][0] -prices[0];dp[0][1] 0;for(int i 1;i n;i){//注意这里不是dp[i - 1][1] - prices[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[n - 1][1];}
} ②.暴力解法相对简单这里给出解题过程
代码详解
class Solution {public int maxProfit(int[] prices) {int cost Integer.MAX_VALUE;int profit 0;for(int price : prices){cost Math.min(cost,price);profit Math.max(profit,price - cost);}return profit;}
}
运行结果 二.买卖股票的最佳时机含冷冻期
题目链接309. 买卖股票的最佳时机含冷冻期 - 力扣LeetCode问题描述 给定一个整数数组prices其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票: 卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 动态规划解法 一.状态表示dp[ i ][ j ]:由于有「买⼊」「可交易」「冷冻期」三个状态因此我们可以选择⽤三个数组其中 dp[i][0] 表⽰第 i 天结束后处于「买⼊」状态此时的最⼤利润dp[i][1] 表⽰第 i 天结束后处于「可交易」状态此时的最⼤利润dp[i][2] 表⽰第 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]前面一天是买入状态今天选择卖出今天过后是冷冻期 三.初始化 dp[0][0] - prices[0] dp[0][1] 0 dp[0][2] 0; 四.填表顺序从左往右从上往下依次填写三个表 五.返回值状态转移方程三者的最大值 max(dp[n - 1][1], dp[n - 1] [2]);dp[n - 1][0]不可能是最大值这里不用考虑进去如果考虑进去了也没关系 各个状态关系图 代码详解 class Solution {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值public int maxProfit(int[] prices) {int n prices.length;int[][] dp new int[n][3];dp[0][0] -prices[0];for(int i 1;i n;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][2]);dp[i][2] dp[i - 1][0] prices[i];}return Math.max(dp[n - 1][1],dp[n - 1][2]);}
} 运行结果 三.买卖股票的最佳时期含⼿续费
题目链接714. 买卖股票的最佳时机含手续费 - 力扣LeetCode
题目描述
给定一个整数数组 prices其中 prices[i]表示第 i 天的股票价格 整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易但是你每笔交易都需要付手续费。如果你已经购买了一个股票在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意这里的一笔交易指买入持有并卖出股票的整个过程每笔交易你只需要为支付一次手续费。 动态规划解法 一.状态表示由于有「买⼊」「可交易」两个状态因此我们可以选择⽤两个数组来定义我们的状态或则一个二维数组也行其中 f[i] 表⽰第 i 天结束后处于「买⼊」状态此时的最⼤利润g[i] 表⽰第 i 天结束后处于「卖出」状态此时的最⼤利润. 二.状态转移方程 我们选择在「卖出」的时候⽀付这个⼿续费那么在「买⼊」的时候就不⽤再考虑⼿续费的问题完成一次交易支付手续费 f[i] max(f[i - 1], g[i - 1] - prices[i]) ①.在 i - 1 天「持有」股票第 i 天啥也不⼲。此时最⼤收益为 f[i - 1] ②.在 i - 1 天的时候「没有」股票在第 i 天买⼊股票。此时最⼤收益为 g[i - 1] - prices[i]) g[i] max(g[i - 1], f[i - 1] prices[i] - fee);①.在 i - 1 天「持有」股票但是在第 i 天将股票卖出。此时最⼤收益为 f[i - 1] prices[i] - fee) 记得⼿续费②.在 i - 1 天「没有」股票然后第 i 天啥也不⼲。此时最⼤收益为 g[i - 1] 三.初始化由于需要⽤到前⾯的状态因此需要初始化第⼀个位置: 对于 f[0] 此时处于「买⼊」状态因此 f[0] -prices[0]对于 g[0] 此时处于「没有股票」状态啥也不⼲即可获得最⼤收益因此 g[0] 0 四.填表顺序从左到右两个表一起填 五.返回值应该返回「卖出」状态下最后⼀天的最⼤值收益 g[n - 1] 代码详解 class Solution {public int maxProfit(int[] prices, int fee) {int n prices.length;int[] f new int[n];int[] g new int[n];f[0] -prices[0];for(int i 1;i n;i){f[i] Math.max(f[i - 1],g[i - 1] - prices[i]);g[i] Math.max(g[i - 1],f[i - 1] prices[i] - fee);}return Math.max(f[n - 1],g[n - 1]);}
} 运行结果 四.买卖股票的最佳时机III:
题目链接123. 买卖股票的最佳时机 III - 力扣LeetCode
题目描述
给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 动态规划解法 一.状态表示由于有「买⼊」「可交易」两个状态因此我们可以选择⽤两个数组。但是这道题⾥⾯还有交易次 数的限制因此我们还需要再加上⼀维⽤来表⽰交易次数。其中 f[i][j] 表⽰第 i 天结束后完成了 j 次交易处于「买⼊」状态此时的最⼤利 润g[i][j] 表⽰第 i 天结束后完成了 j 次交易处于「卖出」状态此时的最⼤利 润。 二.状态转移方程 f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i]);①.在 i - 1 天的时候交易了 j 次处于「买⼊」状态第 i 天啥也不⼲即可。此时最 ⼤利润为 f[i - 1][j] ②.在 i - 1 天的时候交易了 j 次处于「卖出」状态第 i 天的时候把股票买了。此 时的最⼤利润为 g[i - 1][j] - prices[i] 。g[i][j] g[i - 1][j]; if(j 0) g[i][j] max(g[i][j], f[i - 1][j - 1] prices[i]); ①.在 i - 1 天的时候交易了 j 次处于「卖出」状态第 i 天啥也不⼲即可。此时的 最 ⼤利润为 g[i - 1][j] ②.在 i - 1 天的时候交易了 j - 1 次处于「买⼊」状态第 i 天把股票卖了然 后就完 成了 j ⽐交易。此时的最⼤利润为 f[i - 1][j - 1] prices[i] 。但 是这个状态不⼀定存 在要先判断⼀下。 三.初始化 当处于第 0 天的时候只能处于「买⼊过⼀次」的状态此时的收益为 -prices[0] 因 此 f[0][0] - prices[0] 。为了取 max 的时候⼀些不存在的状态「起不到⼲扰」的作⽤我们统统将它们初始化为 - INF ⽤ INT_MIN 在计算过程中会有「溢出」的⻛险这⾥ INF 折半取 0x3f3f3f3f ⾜够⼩即可 四.填表顺序从「上往下填」每⼀⾏每⼀⾏「从左往右」两个表「⼀起填」。 五.返回值返回处于「卖出状态」的最⼤值但是我们也「不知道是交易了⼏次」因此返回 g 表最后⼀⾏ 的最⼤值。 代码详解 class Solution {static int INF -0x3f3f3f3f;public int maxProfit(int[] prices) {int n prices.length;int[][] f new int[n][3];int[][] g new int[n][3];//1.f[0][0] -prices[0];for(int i 1;i f[0].length;i){f[0][i] INF;}for(int j 1;j g[0].length;j){g[0][j] INF;//Integer.MIN_VALUE/2}//2.for(int i 1;i n;i){for(int j 0;j 3;j){f[i][j] Math.max(f[i - 1][j],g[i - 1][j] - prices[i]);g[i][j] g[i - 1][j];if(j 0){g[i][j] Math.max(g[i][j],f[i - 1][j - 1] prices[i]);}}}int res Integer.MIN_VALUE;for(int j 0;j 3;j){ res Math.max(res,g[n - 1][j]);}return res;}
} 运行结果 五.买卖股票的最佳时机IV:
题目链接188. 买卖股票的最佳时机 IV - 力扣LeetCode
题目描述
给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 动态规划解法 一.状态表示为了更加清晰的区分「买⼊」和「卖出」我们换成「有股票」和「⽆股票」两个状态 f[i][j] 表⽰第 i 天结束后完成了 j 笔交易此时处于「有股票」状态的最⼤收益g[i][j] 表⽰第 i 天结束后完成了 j 笔交易此时处于「⽆股票」状态的最⼤收益 二.状态转移方程 f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i]);①.在 i - 1 天的时候⼿⾥「有股票」并且交易了 j 次。在第 i 天的时候啥也不⼲。 此时的收益为 f[i - 1][j] ②.在 i - 1 天的时候⼿⾥「没有股票」并且交易了 j 次。在第 i 天的时候买了股 票。那么 i 天结束之后我们就有股票了。此时的收益为 g[i - 1][j] - prices[i];g[i][j] max(g[i - 1][j], f[i - 1][j - 1] prices[i]);①.在 i - 1 天的时候⼿⾥「没有股票」并且交易了 j 次。在第 i 天的时候啥也不 ⼲。此时的收益为 g[i - 1][j] ②.在 i - 1 天的时候⼿⾥「有股票」并且交易了 j - 1 次。在第 i 天的时候把 股票卖了。那么 i 天结束之后我们就交易了 j 次。此时的收益为 f[i - 1][j - 1] prices[i] 三.初始化 当处于第 0 天的时候只能处于「买⼊过⼀次」的状态此时的收益为 -prices[0] 因 此 f[0][0] - prices[0]为了取 max 的时候⼀些不存在的状态「起不到⼲扰」的作⽤我们统统将它们初始化为 - INF ⽤ INT_MIN 在计算过程中会有「溢出」的⻛险这⾥ INF 折半取 0x3f3f3f3f ⾜够⼩即可 四.填表顺序从上往下填每⼀⾏每⼀⾏从左往右两个表⼀起填。 五.返回值返回处于卖出状态的最⼤值但是我们也不知道是交易了⼏次因此返回 g 表最后⼀⾏的最⼤ 值 代码详解 class Solution {static int INF -0x3f3f3f3f;public int maxProfit(int k, int[] prices) {int n prices.length;int[][] f new int[n][k 1];int[][] g new int[n][k 1];//1.f[0][0] -prices[0];for(int i 1;i f[0].length;i){f[0][i] INF;//-防止越界g[i - 1][j] - prices[i];}for(int j 1;j g[0].length;j){g[0][j] INF;//Integer.MIN_VALUE/2}//2.for(int i 1;i n;i){for(int j 0;j k 1;j){f[i][j] Math.max(f[i - 1][j],g[i - 1][j] - prices[i]);g[i][j] g[i - 1][j];if(j 0){g[i][j] Math.max(g[i][j],f[i - 1][j - 1] prices[i]);}}}int res Integer.MIN_VALUE;for(int j 0;j k 1;j){ res Math.max(res,g[n - 1][j]);}return res;}
} 运行结果 结语 写博客不仅仅是为了分享学习经历同时这也有利于我巩固知识点总结该知识点由于作者水平有限对文章有任何问题的还请指出接受大家的批评让我改进。同时也希望读者们不吝啬你们的点赞收藏关注你们的鼓励是我创作的最大动力
文章转载自： http://www.morning.txjrc.cn.gov.cn.txjrc.cn http://www.morning.tbnpn.cn.gov.cn.tbnpn.cn http://www.morning.kqzt.cn.gov.cn.kqzt.cn http://www.morning.nlqmp.cn.gov.cn.nlqmp.cn http://www.morning.dxzcr.cn.gov.cn.dxzcr.cn http://www.morning.wxlzr.cn.gov.cn.wxlzr.cn http://www.morning.blfll.cn.gov.cn.blfll.cn http://www.morning.dqpd.cn.gov.cn.dqpd.cn http://www.morning.tkcct.cn.gov.cn.tkcct.cn http://www.morning.grjh.cn.gov.cn.grjh.cn http://www.morning.zylrk.cn.gov.cn.zylrk.cn http://www.morning.rdkqt.cn.gov.cn.rdkqt.cn http://www.morning.hdqqr.cn.gov.cn.hdqqr.cn http://www.morning.lffrh.cn.gov.cn.lffrh.cn http://www.morning.bhmnp.cn.gov.cn.bhmnp.cn http://www.morning.nfnxp.cn.gov.cn.nfnxp.cn http://www.morning.xshkh.cn.gov.cn.xshkh.cn http://www.morning.bpp999.com.gov.cn.bpp999.com http://www.morning.gnkdp.cn.gov.cn.gnkdp.cn http://www.morning.nmkfy.cn.gov.cn.nmkfy.cn http://www.morning.lbxcc.cn.gov.cn.lbxcc.cn http://www.morning.rdmn.cn.gov.cn.rdmn.cn http://www.morning.lnyds.cn.gov.cn.lnyds.cn http://www.morning.mlfgx.cn.gov.cn.mlfgx.cn http://www.morning.qztdz.cn.gov.cn.qztdz.cn http://www.morning.cflxx.cn.gov.cn.cflxx.cn http://www.morning.qkpzq.cn.gov.cn.qkpzq.cn http://www.morning.bplqh.cn.gov.cn.bplqh.cn http://www.morning.jjhrj.cn.gov.cn.jjhrj.cn http://www.morning.ykmg.cn.gov.cn.ykmg.cn http://www.morning.zbkdm.cn.gov.cn.zbkdm.cn http://www.morning.cmhkt.cn.gov.cn.cmhkt.cn http://www.morning.dcccl.cn.gov.cn.dcccl.cn http://www.morning.lnbcx.cn.gov.cn.lnbcx.cn http://www.morning.pljdy.cn.gov.cn.pljdy.cn http://www.morning.drmbh.cn.gov.cn.drmbh.cn http://www.morning.hrjrt.cn.gov.cn.hrjrt.cn http://www.morning.zzfjh.cn.gov.cn.zzfjh.cn http://www.morning.jlrym.cn.gov.cn.jlrym.cn http://www.morning.yyzgl.cn.gov.cn.yyzgl.cn http://www.morning.lcqrf.cn.gov.cn.lcqrf.cn http://www.morning.pjxw.cn.gov.cn.pjxw.cn http://www.morning.hjlsll.com.gov.cn.hjlsll.com http://www.morning.mtmph.cn.gov.cn.mtmph.cn http://www.morning.lzqxb.cn.gov.cn.lzqxb.cn http://www.morning.nfks.cn.gov.cn.nfks.cn http://www.morning.mmosan.com.gov.cn.mmosan.com http://www.morning.cwyfs.cn.gov.cn.cwyfs.cn http://www.morning.wnhml.cn.gov.cn.wnhml.cn http://www.morning.qpxrr.cn.gov.cn.qpxrr.cn http://www.morning.llxqj.cn.gov.cn.llxqj.cn http://www.morning.c-ae.cn.gov.cn.c-ae.cn http://www.morning.lxhrq.cn.gov.cn.lxhrq.cn http://www.morning.qkdbz.cn.gov.cn.qkdbz.cn http://www.morning.hmqmm.cn.gov.cn.hmqmm.cn http://www.morning.fbjnr.cn.gov.cn.fbjnr.cn http://www.morning.jfnlj.cn.gov.cn.jfnlj.cn http://www.morning.frtt.cn.gov.cn.frtt.cn http://www.morning.xkhxl.cn.gov.cn.xkhxl.cn http://www.morning.jmmzt.cn.gov.cn.jmmzt.cn http://www.morning.bzgpj.cn.gov.cn.bzgpj.cn http://www.morning.kjlia.com.gov.cn.kjlia.com http://www.morning.yrngx.cn.gov.cn.yrngx.cn http://www.morning.bmqls.cn.gov.cn.bmqls.cn http://www.morning.weitao0415.cn.gov.cn.weitao0415.cn http://www.morning.zfzgp.cn.gov.cn.zfzgp.cn http://www.morning.irqlul.cn.gov.cn.irqlul.cn http://www.morning.pqnps.cn.gov.cn.pqnps.cn http://www.morning.llsrg.cn.gov.cn.llsrg.cn http://www.morning.cqyhdy.cn.gov.cn.cqyhdy.cn http://www.morning.zymgs.cn.gov.cn.zymgs.cn http://www.morning.gjlst.cn.gov.cn.gjlst.cn http://www.morning.qfrmy.cn.gov.cn.qfrmy.cn http://www.morning.dkfrd.cn.gov.cn.dkfrd.cn http://www.morning.rjcqb.cn.gov.cn.rjcqb.cn http://www.morning.ejknty.cn.gov.cn.ejknty.cn http://www.morning.kgfsz.cn.gov.cn.kgfsz.cn http://www.morning.gywxq.cn.gov.cn.gywxq.cn http://www.morning.mypxm.com.gov.cn.mypxm.com http://www.morning.pqwhk.cn.gov.cn.pqwhk.cn
