Open alittlepeara opened 2 months ago
能不能解决这个问题:给定一个整数数组 prices,其中 prices[i]表示第 i 天的股票价格 (单位股票);整数 fee 代表了交易股票的手续费用。你每天最多可以完成10笔交易(包括买与卖),但是你每笔交易都需要付手续费。你最多只能持有20个单位股票,否则你就不能再继续购买股票了。设计一个算法,计算你能获得利润的最大值。要求:你初始持有股票单位为0,随机生成prices数组,数组元素个数500 ≤ N ≤ 1000,数组第i个元素(第i天股票价格)值1 ≤ prices[i] ≤ 100,10 ≤ fee ≤ 20。
121. 买卖股票的最佳时机(一天买一天卖)
题目
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。 设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
思路
555感觉动态规划计算每一个i的时候也都要遍历之前所有的数,和暴力解法复杂度一样,超出时间限制了
为了体现动规的优势,递推方程应该只与前一项的结果有关,不需要看再之前的
代码随想录的解法: 二维数组,dp[i][0]表示持有股票,dp[i][1]表示不持有股票的最大值
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]);
这样就不用再去遍历之前的了122. 买卖股票的最佳时机 II(多次买卖)
题目
给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。返回 你能获得的 最大 利润 。
思路
跟上面一样,唯一要修改的就是
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
因为上面那题只能买一次,所以买的时候默认之前的总金额是0,直接就是-prices[i]代码
123. 买卖股票的最佳时机 III(最多两次买卖)
题目
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
思路
还是想不出来TT 代码随想录: dp[i][0] 不操作 (其实是多余的,可以不要,只是为了完整性) dp[i][1] 第一次持有(不一定是当天买入,可以是延续之前的状态) dp[i][2] 第一次不持有 dp[i][3] 第二次持有 dp[i][4] 第二次不持有
⚠自己按照这个思路写了一遍结果错了,发现是因为没有算当天买卖的情况,所以即使是第一天也可以有所有的状态,所以初始情况需要全部定义
dp[0][1] = -prices[0]; dp[0][3] = -prices[0];
(剩下的都是0)代码
188. 买卖股票的最佳时机 IV(买卖k次)
题目
给你一个整数数组 prices 和一个整数 k ,其中 prices[i] 是某支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
思路
其实和上面那个一样,就是加了循环来写更多的状态
代码