121. 買賣股票的最佳時機
122. 買賣股票的最佳時機 II
123. 買賣股票的最佳時機 III
188. 買賣股票的最佳時機 IV
309. 最佳買賣股票時機含冷凍期
714. 買賣股票的最佳時機含手續(xù)費
以188. 買賣股票的最佳時機 IV 為例講解蝎毡，因為其他題可以通過這道題演化出來跺株。
dp[i][k][0 or 1] (0 <= i <= n-1, 1 <= k <= K)
i 為天數(shù)
k 為最多交易次數(shù) [0,1] 為是否持有股票
總狀態(tài)數(shù): n * K * 2 種狀態(tài)
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
狀態(tài)轉(zhuǎn)移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
max( 選擇 rest , 選擇 sell )
解釋:今天我沒有持有股票坑夯，有兩種可能:
- 我昨天就沒有持有进鸠，然后今天選擇 rest胧奔，所以我今天還是沒有持有;
- 我昨天持有股票沪编，但是今天我 sell 了贫途，所以我今天沒有持有股票了擂达。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
max( 選擇 rest , 選擇 buy )
解釋:今天我持有著股票绢淀，有兩種可能:
- 我昨天就持有著股票萤悴，然后今天選擇 rest，所以我今天還持有著股票;
- 我昨天本沒有持有皆的，但今天我選擇 buy稚疹，所以今天我就持有股票了。
初始狀態(tài):
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity
狀態(tài)轉(zhuǎn)移方程:
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])
121. 買賣股票的最佳時機
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) {
return 0;
}
int k = 1;
int[][][] dp = new int[n][k + 1][2];
dp[0][k][0] = 0;
dp[0][k][1] = -prices[0];
for (int i = 1; i < n; i++) {
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
}
return dp[n - 1][k][0];
}
對于k=1祭务，dp[i-1][0][0] = 0(表示沒有買過股票并且當(dāng)前沒有持有股票),可以化簡去掉所有 k：
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) {
return 0;
}
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], -prices[i]);
}
return dp[n - 1][0];
}
狀態(tài)轉(zhuǎn)移方程的新狀態(tài)只和相鄰的一個狀態(tài)有關(guān)内狗，其實不用整個 dp 數(shù)組，只需要一個變量儲存相鄰的那個狀態(tài)就足夠了义锥，這樣可以把空間復(fù)雜度降到 O(1):
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) {
return 0;
}
int dp_i_0 = 0;
int dp_i_1 = -prices[0];
for (int i = 1; i < n; i++) {
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, -prices[i]);
}
return dp_i_0;
}
122. 買賣股票的最佳時機 II
k 為正無窮柳沙，那么就可以認為 k 和 k - 1 是一樣的“璞叮可以這樣改寫框架：
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])
= max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
我們發(fā)現(xiàn)數(shù)組中的 k 已經(jīng)不會改變了赂鲤，也就是說不需要記錄 k 這個狀態(tài)了：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) {
return 0;
}
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];
}
使用變量存儲：
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) {
return 0;
}
int dp_i_0 = 0;
int dp_i_1 = -prices[0];
for (int i = 1; i < n; i++) {
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, dp_i_0 - prices[i]);
}
return dp_i_0;
}
123. 買賣股票的最佳時機 III
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) {
return 0;
}
int max_k = 2;
int[][][] dp = new int[n][max_k + 1][2];
for (int i = 1; i < n; i++) {
for (int k = max_k; k >= 1; k--) {
dp[0][k][0] = 0;
dp[0][k][1] = -prices[0];
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
}
}
return dp[n - 1][max_k][0];
}
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) {
return 0;
}
int[][][] dp = new int[n][3][2];
dp[0][2][0] = 0;
dp[0][1][0] = 0;
dp[0][1][1] = -prices[0];
dp[0][2][1] = -prices[0];
for (int i = 1; i < n; i++) {
dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i]);
dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i]);
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i]);
dp[i][1][1] = Math.max(dp[i - 1][1][1], -prices[i]);
}
return dp[n - 1][2][0];
}
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int dp_i10 = 0;
int dp_i20 = 0;
// int dp_i11 = Integer.MIN_VALUE;
// int dp_i21 = Integer.MIN_VALUE;
int dp_i11 = -prices[0];
int dp_i21 = -prices[0];
for (int price : prices) {
dp_i20 = Math.max(dp_i20, dp_i21 + price);
dp_i21 = Math.max(dp_i21, dp_i10 - price);
dp_i10 = Math.max(dp_i10, dp_i11 + price);
dp_i11 = Math.max(dp_i11, -price);
}
return dp_i20;
}
188. 買賣股票的最佳時機 IV
public int maxProfit(int max_k, int[] prices) {
int n = prices.length;
if (n == 0) {
return 0;
}
if (max_k > n / 2)// 超出內(nèi)存限制
return maxProfit_k_inf(prices);
int[][][] dp = new int[n][max_k + 1][2];
for (int i = 1; i < n; i++)
for (int k = max_k; k >= 1; k--) {
dp[0][k][0] = 0;
dp[0][k][1] = -prices[0];
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
}
return dp[n - 1][max_k][0];
}
int maxProfit_k_inf(int[] prices) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
}
return dp_i_0;
}
