买卖股票的最佳时机III

题目链接

买卖股票的最佳时机III

题目描述

注意点

• 1 <= prices.length <= 100000
• 0 <= prices[i] <= 100000
• 不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）
• 最多可以完成 两笔 交易

解答思路

• 本题最多可以完成两笔交易，所以在任意一天，都会有五种状态，分别是无操作、第一次买入、第一次卖出、第二次买入、第二次卖出。需要注意的是，当天同时买入卖出是无意义的，利润不会改变，仅仅是增加了交易次数，不在考虑范围之内。同时无操作的利润始终为0，可以忽略不记，所以将每一天都分割成其余四种状态
• 关键是怎么通过第i - 1天推出第i天四种状态的最大利润，可以分为以下几种
  • 当处于第一次买入的状态，其可能是当天购入也可能是之前就已经购入，取决于哪天购买的成本更低，所以dp[i][0] = Math.max(dp[i - 1][0], -prices[i])，注意当天购入的话需要花费prices[i]的成本，所以为负数
  • 当处于第一次卖出的状态，其可能是当天买出也可能是之前就已经卖出，取决于哪天卖出的利润更高，所以dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i])，dp[i - 1][0]是第一次购买最低的成本，其可以保证当天卖出在前i天当中所得到的利润是最大的
  • 当处于第二次买入的状态，其与第一次买入的状态类似，区别是第一次已经交易成功了，所以如果当天买入的话dp[i][2]的值还要加上第一次交易所得到的最大利润，也就是dp[i - 1][1]，所以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[0][2]与dp[0][0]一样，初始需要给默认值-prices[0]，在第一次交易未完成时，dp[i][2]实际上始终与dp[i][0]相同，dp[i][3]与dp[i][1]也是如此，实际上此时第二次交易也是第一次交易（因为dp[i - 1][1]始终都为0，此时dp[i][2] = Math.max(dp[i - 1][2], - prices[i])）。当第一次交易完成时，dp[i][2]就需要在第一次交易获得利润的基础上进行考虑，其购买的成本会变为dp[i - 1][1] - prices[i]

代码

class Solution {public int maxProfit(int[] prices) {int n = prices.length;// 二维数组，dp[i][j]表示第i天时处于第j中状态的最大利润/*** j有以下四种状态* 0：第一次买入股票* 1：第一次卖出股票（也就是完成第一次交易）* 2：第二次买入股票* 3：第二次卖出股票（也就是完成第二次交易）* 不做任何操作也是一种状态，但是对结果无影响不考虑*/int[][] dp = new int[n][4];dp[0][0] = -prices[0];dp[0][2] = -prices[0];for (int i = 1; i < n; i++) {// 第i天购买或者之前就已购买，取购买花费更低的成本dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);// 第i天卖出或者之前就已卖出，取卖出得到更高的利润dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);// 第i天购买或者之前就已购买，取购买花费更低的成本，第二次交易还要加上第一次交易所得的利润dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]);// 第i天卖出或者之前就已卖出，取卖出得到更高的利润dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);}return Math.max(dp[n - 1][1], dp[n - 1][3]);}
}

关键点

• 动态规划的思想
• 每天买卖股票的四种状态
• 怎么根据dp[i - 1][j]推出dp[i][j]