写点什么

LeetCode 题解:188. 买卖股票的最佳时机 IV,动态规划,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 03 月 02 日
LeetCode题解:188. 买卖股票的最佳时机 IV,动态规划,JavaScript,详细注释

原题链接:188. 买卖股票的最佳时机 IV


解题思路:


该题与123. 买卖股票的最佳时机 III类似,只是交易次数有2次改为了k次。如果没有思路可以先看123题的[题解](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/leetcodeti-jie-123-mai-mai-gu-piao-de-zu-xf0n/)


  1. 截至第i天,当前已经交易过 2 次,每次交易都可以买(支出prices[i])或卖(收入prices[i]),因此可以用长度为 k * 2dp数组递推。

  2. 每种交易,都要在之前交易的基础上进行,例如只有买入后,才可以卖出。因此状态转移方程为:


// j为遍历dp的索引// 0~i天,交易k次的状态,每次买入或卖出,都在上一次交易的基础上进行dp[j] = Math.max(    dp[j], // 0~i-1天的状态    dp[j - 1] + (j & 1 ? price : -price), // 第i天的状态);
复制代码


  1. 卖出k次获得的利润一定是最多的,因此最大利润就在dp[dp.length - 1]


/** * @param {number} k * @param {number[]} prices * @return {number} */var maxProfit = function (k, prices) {  // 一共可以交易2次,每次有买卖两种状态,因此需要用k*2种状态递推  let dp = new Array(k * 2);
// 偶数位置为买入,第一次买入需要支出prices[0] // 奇数位置为卖出,由于没有买入过股票,没法卖出,为0 for (let i = 0; i < dp.length; i++) { dp[i] = i & 1 ? 0 : -prices[0]; }
// 从i=1天开始,递推每天的交易情况 for (let i = 1; i < prices.length; i++) { const price = prices[i]; // 缓存当天的价格
// 0~i天,只买入1次的最优状态,第一次交易没有前置状态 dp[0] = Math.max(dp[0], -price);
// 0~i天,交易k次的状态,每次买入或卖出,都在上一次交易的基础上进行 for (let j = 1; j < dp.length; j++) { dp[j] = Math.max( dp[j], // 0~i-1天的状态 dp[j - 1] + (j & 1 ? price : -price), // 第i天的状态 ); } }
// 卖出次数最多时,利润也最大。 // k为0时,利润为0 return dp[dp.length - 1] || 0;};
复制代码


发布于: 2021 年 03 月 02 日阅读数: 15
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:188. 买卖股票的最佳时机 IV,动态规划,JavaScript,详细注释