江苏连云港网站制作公司,网站如何做百度百科,wordpress 时间设置,网络文明安全行动题目链接
买卖股票的最佳时机III
题目描述 注意点
1 prices.length 1000000 prices[i] 100000不能同时参与多笔交易#xff08;必须在再次购买前出售掉之前的股票#xff09;最多可以完成 两笔 交易
解答思路
本题最多可以完成两笔交易#xff0c;…题目链接
买卖股票的最佳时机III
题目描述 注意点
1 prices.length 1000000 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]
