解题思路分析
利用三维DP数组来构建状态关系dp[n+1][k+1][2]
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
第i天不持有股票：第i-1天就不持有，或者第i-1天持有，又卖了
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);---在buy时令操作数k-1
第i天持有股票：第i-1天就持有，或者第i-1天不持有，第i天买入了
base case：
当i=0时，等价于第0天，还没有开始。则不持有的收益为0.持有的状态不可能，用最小值来表示收益代表不可能
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
class Solution {
public int maxProfit(int[] prices) {
int n=prices.length;
if(n<2) return 0;//无法完成交易
/* k=1;
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
=max(dp[i-1][1][0],dp[i-1][1][1]+prices[i]);
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);
=max(dp[i-1][1][1],dp[i-1][1-1=0][0]-prices[i]);---在buy时令操作数k-1
*/
int[][] dp=new int[n+1][2];
//base case:第0天不持有股票收益为0，不可能持有股票，用最小数代替
dp[0][0]=0;
dp[0][1]=Integer.MIN_VALUE;
for(int i=1;i<=n;i++){//注意dp的i不是prices的i
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
dp[i][1]=Math.max(dp[i-1][1],-prices[i-1]);
}
return dp[n][0];
}
}122. 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution {
public int maxProfit(int[] prices) {
/* k=无数大（可以视k=k-1）;
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
=max(dp[i-1][K][0],dp[i-1][K][1]+prices[i]);
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);
=max(dp[i-1][K][1],dp[i-1][K][0]-prices[i]);---在buy时令操作数k-1
省去k坐标
*/
int n=prices.length;
if(n<2) return 0;
int[][] dp=new int[n+1][2];
//base case:
dp[0][0]=0;
dp[0][1]=Integer.MIN_VALUE;
for(int i=1;i<=n;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i-1]);
}
return dp[n][0];
}
public int maxProfit1(int[] prices) {
int n=prices.length;
if(n < 2) return 0;
int ans=0;
for(int i=1;i<n;i++){
int diff=prices[i]-prices[i-1];
if(diff>0){
ans+=diff;
}
}
return ans;
}
}123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution {
public int maxProfit(int[] prices) {
/* k=2;1：没有股票，2：有股票
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);---在buy时令操作数k-1
我们可以穷举k的取值
*/
int n=prices.length;
if(n<2) return 0;
int[][][] dp=new int[n+1][2][2];
//base case:
dp[0][0][0]=dp[0][1][0]=0;
dp[0][0][1]=dp[0][1][1]=Integer.MIN_VALUE;
for(int i=1;i<=n;i++){
dp[i][0][0]=Math.max(dp[i-1][0][0],dp[i-1][0][1]+prices[i-1]);//-buy
dp[i][0][1]=Math.max(dp[i-1][0][1],-prices[i-1]);
dp[i][1][0]=Math.max(dp[i-1][1][0],dp[i-1][1][1]+prices[i-1]);//-buy
dp[i][1][1]=Math.max(dp[i-1][1][1],dp[i-1][0][0]-prices[i-1]);
}
return dp[n][1][0];
}
//优化代码--只和相邻状态有关，则记录相邻状态
public int maxProfit1(int[] prices) {
int n=prices.length;
int buy1=-prices[0],sell1=0;
int buy2=-prices[0],sell2=0;
for(int i=1;i<n;i++){
buy1=Math.max(buy1,-prices[i]);
sell1=Math.max(sell1,buy1+prices[i]);
buy2=Math.max(buy2,sell1-prices[i]);
sell2=Math.max(sell2,buy2+prices[i]);
}
return sell2;
}
}188. 买卖股票的最佳时机 IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution {
public int maxProfit(int k, int[] prices) {
int n=prices.length;
if(n < 2) return 0;
//k如果可以超过n/2,则和k为无穷大效果一样，用辅助函数求解
if(k > n/2) return maxProfit_help(prices);
//借助于三维DP来解决
int[][][] dp=new int[n+1][k+1][2];
//base case:处理i=0的情况
for(int i=1;i<=k;i++){
dp[0][i][0]=0;
dp[0][i][1]=Integer.MIN_VALUE;
}
for(int i=1;i<=n;i++){
for(int j=k;j>=1;j--){
dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);
dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);
}
}
return dp[n][k][0];
}
public int maxProfit_help(int[] prices) {
/* k=无数大（可以视k=k-1）;
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
=max(dp[i-1][K][0],dp[i-1][K][1]+prices[i]);
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);
=max(dp[i-1][K][1],dp[i-1][K][0]-prices[i]);---在buy时令操作数k-1
省去k坐标
*/
int n=prices.length;
if(n<2) return 0;
int[][] dp=new int[n+1][2];
//base case:
dp[0][0]=0;
dp[0][1]=Integer.MIN_VALUE;
for(int i=1;i<=n;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i-1]);
}
return dp[n][0];
}
}** 309. 最佳买卖股票时机含冷冻期**
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
class Solution {
public int maxProfit(int[] prices) {
/* k=无穷大;1：没有股票，2：有股票
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);-sell
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);---在buy时令操作数k-1
含冷冻期则在买入时，和一天前的情况有关
即：
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);-sell
dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i]);
*/
int n=prices.length;
if(n < 2) return 0;
int[][] dp=new int[n+1][2];
//base case:列举第0天和第1天（因为冷冻期一天）
dp[0][0]=0;
dp[0][1]=Integer.MIN_VALUE;
dp[1][0]=0;
dp[1][1]=-prices[0];
for(int i=2;i<=n;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i-1]);
}
return dp[n][0];
}
}714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
class Solution {
public int maxProfit(int[] prices, int fee) {
/* k=无穷大;1：没有股票，2：有股票
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);-sell
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);---在buy时令操作数k-1
含手续费则在买入时，收益减去手续费
即：
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);-sell
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]-fee);
*/
int n=prices.length;
if(n < 2) return 0;
int[][] dp=new int[n+1][2];
//base case:
dp[0][0]=0;
dp[0][1]=Integer.MIN_VALUE;
for(int i=1;i<=n;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i-1]-fee);
}
return dp[n][0];
}
}
京公网安备 11010502036488号