My Eighty-seventh Page - 买卖股票的最佳时机 - By Nicolas
admin
2024-03-04 15:47:37
0次

这篇page是针对leetcode上的188.买卖股票的最佳时机Ⅳ所写的。小尼先简单的说明一下这道题的意思,就是我们给定一个整数数组prices,它的第i个元素prices[i]是一支给的股票在第i天的价格。我们需要设计一个算法在我们完成k次交易的情况下我们可以赚到最大的利润。

其实这道题跟小尼上面的所写的只交易两次的题目非常的类似,只是说我们增加了交易的次数,意味着我们进行的操作没多一次交易我们将会进行的步骤就回增加两次,我们还是利用动态规划五部曲:

1.确定dp数组以及下标的含义

在动态规划:123.买卖股票的最佳时机III (opens new window)中,我是定义了一个二维dp数组,本题其实依然可以用一个二维dp数组。

使用二维数组 dp[i][j] :第i天的状态为j,所剩下的最大现金是dp[i][j]

j的状态表示为:

  • 0 表示不操作
  • 1 第一次买入
  • 2 第一次卖出
  • 3 第二次买入
  • 4 第二次卖出
  • .....

大家应该发现规律了吧 ,除了0以外,偶数就是卖出,奇数就是买入。

题目要求是至多有K笔交易,那么j的范围就定义为 2 * k + 1 就可以了。

2.确定递推公式

还要强调一下:dp[i][1],表示的是第i天,买入股票的状态,并不是说一定要第i天买入股票,这是很多同学容易陷入的误区。

达到dp[i][1]状态,有两个具体操作:

  • 操作一:第i天买入股票了,那么dp[i][1] = dp[i - 1][0] - prices[i]
  • 操作二:第i天没有操作,而是沿用前一天买入的状态,即:dp[i][1] = dp[i - 1][1]

选最大的,所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作:

  • 操作一:第i天卖出股票了,那么dp[i][2] = dp[i - 1][1] + prices[i]
  • 操作二:第i天没有操作,沿用前一天卖出股票的状态,即:dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

3.dp数组如何初始化

第0天没有操作,这个最容易想到,就是0,即:dp[0][0] = 0;

第0天做第一次买入的操作,dp[0][1] = -prices[0];

第0天做第一次卖出的操作,这个初始值应该是多少呢?

首先卖出的操作一定是收获利润,整个股票买卖最差情况也就是没有盈利即全程无操作现金为0,

从递推公式中可以看出每次是取最大值,那么既然是收获利润如果比0还小了就没有必要收获这个利润了。

所以dp[0][2] = 0;

第0天第二次买入操作,初始值应该是多少呢?

不用管第几次,现在手头上没有现金,只要买入,现金就做相应的减少。

第二次买入操作,初始化为:dp[0][3] = -prices[0];

所以同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0],在初始化的地方同样要类比j为偶数是卖、奇数是买的状态。

4.确定遍历顺序

从递归公式其实已经可以看出,一定是从前向后遍历,因为dp[i],依靠dp[i - 1]的数值。

5.导出递推公式

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

class Solution {public int maxProfit(int k, int[] prices) {if(prices.length == 0) return 0;int len = prices.length;int[][] dp = new int[len][k*2 + 1];for(int i = 1;i < k*2; i += 2){dp[0][i] = -prices[0];}for(int i = 1;i < len ; i++){for(int j = 0; j < k*2 - 1; j += 2){dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); }}return dp[len - 1][k*2];}
}

小尼简单的说明一下这道题的解题的思路,其实还是比较简单的,其实就是我们在两层递归中我们一共是进行两部操作,我们只是再将步数进行不断的重复,我们进行的第一步就是买入,这里就是对应我们的j+1的操作,我们第二步就是做卖出的操作,这里对应的步骤就是j+2的操作。我们第一层递归的是我们的物品数,我们的第二层递归的是我们的k的层数,因为每当我们增加一次交易的机会,我们的步骤就会增加两个,所以我们再循环中所设的限制就是j < k*2 - 1.

希望上面的代码可以帮助到小伙伴们~~~

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...