題目

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

題解

經(jīng)典的 暴力遞歸 -> 傻緩存 -> DP，重要思路來源于之前做過的 leetcode 309. Best Time to Buy and Sell Stock with Cooldown | 309. 最佳買賣股票時機含冷凍期（動態(tài)規(guī)劃）

當(dāng)年看答案也摸不清門路的 dp，現(xiàn)在應(yīng)不是玄學(xué)了，哈哈。

將「買入」和「賣出」分開進(jìn)行考慮：「買入」為負(fù)收益，而「賣出」為正收益。在初入股市時，你只有「買入」的權(quán)利，只能獲得負(fù)收益。而當(dāng)你「買入」之后，你就有了「賣出」的權(quán)利，可以獲得正收益。顯然，我們需要盡可能地降低負(fù)收益而提高正收益，因此我們的目標(biāo)總是將收益值最大化。因此，我們可以使用動態(tài)規(guī)劃的方法，維護(hù)在股市中每一天結(jié)束后可以獲得的「累計最大收益」，并以此進(jìn)行狀態(tài)轉(zhuǎn)移，得到最終的答案。

沒有草稿，直接上代碼：

class Solution {public int maxProfit(int[] prices, int fee) {// Approach 1: Recursive, Brute Force // return process1(prices, 0, false,fee);// Approach 2: Recursion with Memoization // int[][] dp = new int[2][prices.length + 1]; // Arrays.fill(dp[0], Integer.MIN_VALUE); // Arrays.fill(dp[1], Integer.MIN_VALUE); // dp[0][prices.length] = 0; // dp[1][prices.length] = 0; // return process2(prices, 0, 0, fee, dp);// Approach 3: Dynamic Programmingint[][] dp = new int[2][prices.length + 1];Arrays.fill(dp[0], Integer.MIN_VALUE);Arrays.fill(dp[1], Integer.MIN_VALUE);dp[0][prices.length] = 0;dp[1][prices.length] = 0;for (int i = prices.length - 1; i >= 0; i--) {for (int pending = 0; pending <= 1; pending++) {int p1 = Integer.MIN_VALUE;int p2 = Integer.MIN_VALUE;int p3 = Integer.MIN_VALUE;int p4 = Integer.MIN_VALUE;if (pending == 1) {p1 = dp[1][i + 1]; // 不賣p2 = dp[0][i + 1] + prices[i] - fee; // 賣} else {p3 = dp[1][i + 1] - prices[i]; // 買p4 = dp[0][i + 1]; // 不買}dp[pending][i] = Math.max(Math.max(p1, p2), Math.max(p3, p4));}}return dp[0][0];}// 從i位置開始做決策，獲得的最大收益（pending表示當(dāng)前是否持有股票） // public int process1(int[] prices, int i, boolean pending, int fee) { // if (i == prices.length) return 0; // // int p1 = Integer.MIN_VALUE; // int p2 = Integer.MIN_VALUE; // int p3 = Integer.MIN_VALUE; // int p4 = Integer.MIN_VALUE; // if (pending) {// 持有股票 // p1 = process1(prices, i + 1, true, fee); // 不賣 // p2 = process1(prices, i + 1, false, fee) + prices[i] - fee; // 賣 // } else { // 未持有股票 // p3 = process1(prices, i + 1, true, fee) - prices[i]; // 買 // p4 = process1(prices, i + 1, false, fee); // 不買 // } // return Math.max(Math.max(p1, p2), Math.max(p3, p4)); // }// public int process2(int[] prices, int i, int pending, int fee, int[][] dp) { // if (dp[pending][i] != Integer.MIN_VALUE) return dp[pending][i]; // // int p1 = Integer.MIN_VALUE; // int p2 = Integer.MIN_VALUE; // int p3 = Integer.MIN_VALUE; // int p4 = Integer.MIN_VALUE; // if (pending == 1) {// 持有股票 // p1 = process2(prices, i + 1, 1, fee, dp); // 不賣 // p2 = process2(prices, i + 1, 0, fee, dp) + prices[i] - fee; // 賣 // } else { // 未持有股票 // p3 = process2(prices, i + 1, 1, fee, dp) - prices[i]; // 買 // p4 = process2(prices, i + 1, 0, fee, dp); // 不買 // } // // int result = Math.max(Math.max(p1, p2), Math.max(p3, p4)); // dp[pending][i] = result; // return result; // } }

總結(jié)

以上是生活随笔為你收集整理的leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee | 714. 买卖股票的佳最时机含手续费（递归-＞傻缓存-＞dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。