做淘宝店铺标志的网站,鲁中网站,知乎 wordpress主题,包头市网站建设公司第五十天| 第九章 动态规划 part11 123. 买卖股票的最佳时机III 188. 买卖股票的最佳时机IV
一、123. 买卖股票的最佳时机III#xff08;难难难难难#xff09; 题目链接#xff1a;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/ 题目介绍#xff…第五十天| 第九章 动态规划 part11 123. 买卖股票的最佳时机III 188. 买卖股票的最佳时机IV
一、123. 买卖股票的最佳时机III难难难难难 题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/ 题目介绍 给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。 **注意**你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 示例 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 。思路 注意本题是最多买卖两次股票 DP五部曲 1确定dp数组及下标含义 一天一共就有五个状态 没有操作 其实我们也可以不设置这个状态第一次持有股票第一次不持有股票第二次持有股票第二次不持有股票 dp[i][j]中 i表示第i天j为 [0 - 4] 五个状态dp[i][j]表示第i天状态j所剩最大现金。五个状态分别如下 dp[i][0]: 表示第i天不操作股票的时候手中的最大金额(也就是0)
dp[i][1]: 表示第i天第一次持有该股票手中的最大金额
dp[i][2]: 表示第i天第一次不持有该股票手中的最大金额
dp[i][3]: 表示第i天第二次持有该股票手中的最大金额
dp[i][4]: 表示第i天第二次不持有该股票手中最大的金额2确定递推公式 和I、II一样的思路 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]);
dp[i][4] Math.max(dp[i-1][4], dp[i-1][3]prices[i]);3初始化dp数组 dp[0][0] 0;
dp[0][1] -prices[0];
dp[0][2] 0;
dp[0][3] -prices[0];
dp[0][4] 0;分别表示的含义是
1dp[0][0]第0天没有任何操作手里的金额是0
2dp[0][1]第0天第一次持有股票手里的金额就是买第0天的股票花掉的
3dp[0][2]第0天第一次不持有股票手里的金额就是买完再卖了第0天的股票也就是0
4dp[0][3]为什么会出现第二次持有呢可以当作第一天买了又卖了然后再买
5dp[0][4]同理。4确定遍历顺序 正序 5打印dp数组 代码
class Solution {public int maxProfit(int[] prices) {if (prices null || prices.length 0) return 0;// (1)确定dp数组及下标含义// dp[i][0]: 表示第i天不操作股票的时候手中的最大金额(也就是0)// dp[i][1]: 表示第i天第一次持有该股票手中的最大金额// dp[i][2]: 表示第i天第一次不持有该股票手中的最大金额// dp[i][3]: 表示第i天第二次持有该股票手中的最大金额// dp[i][4]: 表示第i天第二次不持有该股票手中最大的金额int[][] dp new int[prices.length][5];// (3)初始化dp数组dp[0][1] -prices[0];dp[0][3] -prices[0];// (4)确定遍历顺序for (int i 1; i prices.length; i) {// (2)确定递推公式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]);dp[i][4] Math.max(dp[i-1][4], dp[i-1][3]prices[i]);}return dp[prices.length-1][4];}
}注意 这里的返回值再强调一下 首先众所周知你不持有股票手里的金额一定是大于持有股票的所以返回的状态一定是偶数状态。那为什么不返回状态2呢 是因为状态4其实是包含了状态2的因为如果状态2达到最大值状态4一定会保持这个最大值的。因此直接返回状态4即可。
二、188. 买卖股票的最佳时机IV 题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/ 题目介绍 给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。 **注意**你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 示例 1 输入k 2, prices [2,4,1]
输出2
解释在第 1 天 (股票价格 2) 的时候买入在第 2 天 (股票价格 4) 的时候卖出这笔交易所能获得利润 4-2 2 。思路 注意本题是最多买卖k次股票根据上道题可以推算出本题只需要把握一些关键的边界点即可 1dp数组的初始化长度2k12初始化dp数组奇数状态初始为-prices[0]边界是 2 * k3递推公式需要一个j表示状态j从0开始每次循环2因此到最后一位2k时j2k-2。因此j的边界是j 2k - 1; 代码
class Solution {public int maxProfit(int k, int[] prices) {if (prices null || prices.length 0) return 0;int[][] dp new int[prices.length][2*k1];for (int i 1; i 2*k; i 2) {dp[0][i] -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][j1], dp[i-1][j] - prices[i]);dp[i][j 2] Math.max(dp[i-1][j2], dp[i-1][j1] prices[i]);}}return dp[prices.length - 1][2*k];}
}
