給定一個整數數組?prices，其中第?i?個元素代表了第?i?天的股票價格 ；非負整數?fee 代表了交易股票的手續費用。

你可以無限次地完成交易，但是你每次交易都需要付手續費。如果你已經購買了一個股票，在賣出它之前你就不能再繼續購買股票了。

返回獲得利潤的最大值。

示例 1:

輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8
解釋: 能夠達到的最大利潤: ?
在此處買入?prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤:?((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:

0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

思路：

這個問題，每天都有三種「選擇」：買入、賣出、無操作，我們用 buy, sell, rest 表示這三種選擇。但問題是，并不是每天都可以任意選擇這三種選擇的，因為 sell 必須在 buy 之后，buy 必須在 sell 之后。那么 rest 操作還應該分兩種狀態，一種是 buy 之后的 rest（持有了股票），一種是 sell 之后的 rest（沒有持有股票）。而且別忘了，我們還有交易次數 k 的限制，就是說你 buy 還只能在 k > 0 的前提下操作。

很復雜對吧，不要怕，我們現在的目的只是窮舉，你有再多的狀態，老夫要做的就是一把梭全部列舉出來。這個問題的「狀態」有三個，第一個是天數，第二個是允許交易的最大次數，第三個是當前的持有狀態（即之前說的 rest 的狀態，我們不妨用 1 表示持有，0 表示沒有持有）。然后我們用一個三維數組就可以裝下這幾種狀態的全部組合：

dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 為天數，大 K 為最多交易數
此問題共 n × K × 2 種狀態，全部窮舉就能搞定。

for 0 <= i < n:
? ? for 1 <= k <= K:
? ? ? ? for s in {0, 1}:
? ? ? ? ? ? dp[i][k][s] = max(buy, sell, rest)
而且我們可以用自然語言描述出每一個狀態的含義，比如說 dp[3][2][1] 的含義就是：今天是第三天，我現在手上持有著股票，至今最多進行 2 次交易。再比如 dp[2][3][0] 的含義：今天是第二天，我現在手上沒有持有股票，至今最多進行 3 次交易。很容易理解，對吧？

我們想求的最終答案是 dp[n - 1][K][0]，即最后一天，最多允許 K 次交易，最多獲得多少利潤。讀者可能問為什么不是 dp[n - 1][K][1]？因為 [1] 代表手上還持有股票，[0] 表示手上的股票已經賣出去了，很顯然后者得到的利潤一定大于前者。

記住如何解釋「狀態」，一旦你覺得哪里不好理解，把它翻譯成自然語言就容易理解了。

狀態轉移方程：

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，所以今天我就持有股票了。

tips：如果不限制次數，那二維數組即可實現，k可以忽略

提交的代碼：

class Solution {
? ? public int maxProfit(int[] prices, int fee) {
? ? ? ? int min=prices[0];
?? ?int dp[][] = new int[prices.length][2];
?? ?dp[0][0] = 0;
?? ?dp[0][1] = -prices[0];
?? ?for(int i=1;i<prices.length;i++)
?? ?{
?? ??? ?dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]+prices[i]-fee);
?? ??? ?dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
?? ?}
?? ?return dp[prices.length-1][0];
? ? }
}

完整的代碼：

public class Solution714 {
public static int maxProfit(int[] prices, int fee) {
?? ?int min=prices[0];
?? ?int dp[][] = new int[prices.length][2];
?? ?dp[0][0] = 0;
?? ?dp[0][1] = -prices[0];
?? ?for(int i=1;i<prices.length;i++)
?? ?{
?? ??? ?dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]+prices[i]-fee);
?? ??? ?dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
?? ?}
?? ?return dp[prices.length-1][0];
? ? ? ??
? ? }
public static void main(String[] args)
{
?? ?int nums[] = {1, 3, 2, 8, 4, 9};
?? ?int fee = 2;
?? ?//int nums[] = {1,3,7,5,10,3};
?? ?//int fee = 3;
?? ?System.out.println(maxProfit(nums,fee));
}
}
?

總結

以上是生活随笔為你收集整理的Leetcode--714. 买卖股票的最佳时间含手续费的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。