股票问题
我们需要注意的是交易次数k的限制
121. 买卖股票的最佳时机 股票入门题目
只有一次交易机会，我们只需要找到最小价格日和最大价格日即可解决问题
//交易次数k的限制
//k = 1
public int maxProfit(int[] prices) {
int n = prices.length;
int profit = 0, buy = prices[0];
for (int i = 1; i < n; i++) {
profit = Math.max(profit, prices[i] - buy);
buy = Math.min(buy, prices[i]);
}
return profit;
}
122. 买卖股票的最佳时机 II
122则可以进行多次交易，我们需要用dp状态机来解决问题
-
dp[i][0]表示未持有股票
-
dp[i][1]表示持有股票
dp[i][0]状态则从前一天的(未持有 ，持有卖出)转移 ,
dp[i][1]状态则从前一天的(持有，未持有买入)转移
//k = +infinity
public int maxProfitDP(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
//对二维dp进行优化
//每一天的情况只与前一天的有关
public int maxProfit_k_inf(int[] prices){
int n = prices.length;
if (n == 0){
return 0;
}
int dp0 = 0, dp1 = -prices[0];
for (int price : prices) {
dp0 = Math.max(dp0, dp1 + price);
dp1 = Math.max(dp1, dp0 - price);
}
return dp0;
}
//我们注意到题目要求也符合贪心算法
public int maxProfit(int[] prices) {
//只要有赚就卖
int n = prices.length;
int profit = 0;
for (int i = 1; i < n; i++) {
profit += Math.max(0, prices[i] - prices[i - 1]);
}
return profit;
}
714. 买卖股票的最佳时机含手续费
无限次交易，需计算手续费进行判断
我们只需在121的基础上进行修改就好
//k with fee
public int maxProfit_k_fee(int[] prices , int fee){
int n = prices.length;
int profit = 0, buy = -prices[0];
for (int i = 1; i < n; i++) {
profit = Math.max(profit, prices[i] + buy - fee);
buy = Math.max(buy, profit - prices[i]);
}
return profit;
}
309. 最佳买卖股票时机含冷冻期
每次交易后都会有一天的冷冻期才可以进行下一次交易，即有三种状态：未持有，冷冻期，持有
用dp状态机去解决不同0 / 1 / 2三种情况
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) {
return 0;
}
//0:持股，1:卖出进入CD, 2:不持股且不CD
int[][] dp = new int[n][3];
dp[0][0] = -prices[0];
for (int i = 1; i < n; i++) {
//买入，前者是状态1持股未卖出 ， 后者是处于状态2的时候准备卖出
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
//今天卖了，收益是↓
dp[i][1] = dp[i - 1][0] + prices[i];
//dp[i - 1][1]股票之前就卖掉了，前一天是冷冻期 , 后者则是之前卖了且前一天不在CD
dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
}
return Math.max(dp[n - 1][1], dp[n - 1][2]);
}
//优化
//k with cooldown
public int maxProfit_k_cd(int[] prices){
int n = prices.length;
if (n == 0){
return 0;
}
//dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
//dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
//dp[i][]只与dp[i - 1][]有关 ， 用pre去代替
int dp_i_0 = 0 , dp_i_1 = Integer.MIN_VALUE , dp_pre_0 = 0;
for (int price : prices) {
int tmp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + price);
dp_i_1 = Math.max(dp_i_1, dp_pre_0 - price);
dp_pre_0 = tmp;
}
return dp_i_0;
}
123. 买卖股票的最佳时机 III
规定交易次数k = 2
//k = 2
public int maxProfit_k_2(int[] prices){
int n = prices.length;
if (n == 0){
return 0;
}
int dp_i_1_0 = 0 , dp_i_1_1 = Integer.MIN_VALUE , dp_i_2_0 = 0 , dp_i_2_1 = Integer.MIN_VALUE;
for (int price : prices){
dp_i_2_0 = Math.max(dp_i_2_0 , dp_i_2_1 + price);
dp_i_2_1 = Math.max(dp_i_2_1 , dp_i_1_0 - price);
dp_i_1_0 = Math.max(dp_i_1_0 , dp_i_1_1 + price);
dp_i_1_1 = Math.max(dp_i_1_1 , -price);
}
return dp_i_2_0;
}
188. 买卖股票的最佳时机 IV
规定交易次数为k ，123的延伸版本
//k = any integer
public int maxProfit_k(int[] prices , int max_K){
int n = prices.length;
if (n == 0){
return 0;
}else if (n / 2 < max_K){
//若k > n / 2 ,即相当于可以进行无数次交易
return maxProfit_k_inf(prices);//122
}
//n股票天数
//max_k交易次数
//0未持有/1持有
int[][][] dp = new int[n][max_K + 1][2];
//initialize
for (int i = 0; i <= max_K ; i++) {
dp[0][i][1] = -prices[0];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= max_K ; j++) {
dp[i][j][0] = Math.max(dp[i - 1][j][0] , dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1] , dp[i - 1][j - 1][0] - prices[i]);
}
}
return dp[n - 1][max_K][0];
}