My Eighty-fifth Page - 买卖股票的最佳时机Ⅱ - By Nicolas
admin
2024-02-29 21:40:51
0

这篇page是针对leetcode上的122.买卖股票的最佳时机Ⅱ所写的。小尼先简单的说明一下这道题的意思,就是我们给定一个整数prices,其中prices[i]表示某支股票第i天的价格。在每一天,可以决定是否购买或出售股票,在任何时候最多只能持有一股股票。

小尼直接上这道题的动态规划五部曲:

  • dp[i][0] 表示第i天持有股票所得现金。
  • dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来

  • 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
  • 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[i - 1][1] - prices[i]

注意这里和121. 买卖股票的最佳时机 (opens new window)唯一不同的地方,就是推导dp[i][0]的时候,第i天买入股票的情况

在121. 买卖股票的最佳时机 (opens new window)中,因为股票全程只能买卖一次,所以如果买入股票,那么第i天持有股票即dp[i][0]一定就是 -prices[i]。

而本题,因为一只股票可以买卖多次,所以当第i天买入股票的时候,所持有的现金可能有之前买卖过的利润。

那么第i天持有股票即dp[i][0],如果是第i天买入股票,所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即:dp[i - 1][1] - prices[i]。

在来看看如果第i天不持有股票即dp[i][1]的情况, 依然可以由两个状态推出来

  • 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]
  • 第i天卖出股票,所得现金就是按照今天股票佳价格卖出后所得现金即:prices[i] + dp[i - 1][0]

小尼接下来直接拉一下这道题的代码:

class Solution // 实现1:二维数组存储// 可以将每天持有与否的情况分别用 dp[i][0] 和 dp[i][1] 来进行存储// 时间复杂度:O(n),空间复杂度:O(n)public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n][2];     // 创建二维数组存储状态dp[0][0] = 0;                   // 初始状态dp[0][1] = -prices[0];for (int i = 1; i < n; ++i) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);    // 第 i 天,没有股票dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);    // 第 i 天,持有股票}return dp[n - 1][0];    // 卖出股票收益高于持有股票收益,因此取[0]}
}

相关内容

热门资讯

怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...
安卓系统手写%怎样调出,具体实... 你有没有遇到过这种情况:在使用安卓手机的时候,突然想用手写输入法来记录一些灵感或者重要信息,可是怎么...
安卓手机重置 系统设置,轻松恢... 手机用久了是不是感觉卡顿得厉害?别急,今天就来教你怎么给安卓手机来个大变身——重置系统设置!想象你的...
win如何安装安卓系统,Win... 哇,你有没有想过,让你的Win系统也能玩转安卓应用?没错,就是那种在手机上轻松自如的安卓系统,现在也...
苹果qq和安卓系统,跨平台体验... 你有没有发现,现在手机市场上,苹果和安卓的较量可是越来越激烈了呢!咱们就来聊聊这个话题,看看苹果QQ...
显示最好的安卓系统,探索最新旗... 你有没有想过,为什么安卓系统那么受欢迎呢?它就像一个魔法盒子,里面装满了各种神奇的魔法。今天,就让我...
安卓app怎么降级系统,系统版... 你有没有发现,有时候安卓手机的系统更新后,新功能虽然炫酷,但老系统用起来更顺手呢?别急,今天就来教你...
雷军脱离安卓系统,引领科技变革... 你知道吗?最近科技圈可是炸开了锅,因为我们的雷军大大竟然宣布要脱离安卓系统,这可真是让人大跌眼镜啊!...
安卓系统自动开网络,安卓系统自... 你有没有发现,手机里的安卓系统有时候会自动开启网络连接,这可真是让人又爱又恨啊!有时候,你正专心致志...
安卓系统怎样控制后台,因为服务... 手机里的安卓系统是不是感觉越来越卡了?后台程序太多,不仅耗电还影响性能。别急,今天就来教你怎么巧妙地...
安卓系统打游戏推荐,一触即达! 你有没有发现,现在手机游戏越来越好玩了?不管是休闲小游戏还是大型MMORPG,都能在手机上畅玩。但是...