題目

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/

DP 模型套路

DP 套路之：暴力遞歸->傻緩存->DP

DP套路之：暴力遞歸-＞傻緩存-＞DP
1、暴力遞歸過程：遞歸就是嘗試。此時，你的思維邏輯來源于你的自然智慧、你的遞歸代碼具有現實意義。需要注意的是，在遞歸的時候，參數設計很重要，參數的個數直接決定了后續優化后dp的時間復雜度。
2、傻緩存過程：帶緩存的暴力遞歸。緩存可以是結構化的dp數組（狀態有限的時候），或者是哈希表（狀態難以窮舉，或者狀態太多，即便可以窮舉也會超出空間限制），這種記憶化搜索的方法肯定比暴力遞歸要好得多，避免了重復計算。
給暴力遞歸加緩存的時候，參數的含義/代碼含義已經不重要了，緩存的設計可以脫離題意，因為它只是為了避免重復計算而設計的。因此，即便在這一步已經忘了題意，也不妨礙你僅從代碼邏輯上進行改寫。
3、dp過程：去分析位置的嚴格依賴關系，將傻緩存轉化成結構化的dp。這個過程更加套路，尤其是當你從從自頂向下的記憶化搜索變成了自底向上的dp時候，直接把你的邏輯結構翻了過來。你要先填base case，再按照依賴順序逐層填dp表，至此你的dp已經搞定了。
你會驚喜的發現你得到一個所謂的狀態轉移方程，而對于狀態轉移方程的直觀解釋，早已脫離了原始的自然智慧可以得到的遞歸的含義，它也許很短，也許是一個優美的結論，但它只是看起來優美而已，不具有普遍性和啟發性，很難舉一反三、一下想到。

關于記憶化搜索與dp之爭，它們二者時間復雜度同樣的好。只不過記憶化搜索沒有分析誰先依賴誰后依賴，你沒算過你就遞歸去算，你算過你就直接從記憶表里拿值返回。而嚴格表結構的動態規劃是，我嚴格的整理好依賴關系，從這張表的簡單位置填到復雜位置，也就是說它比記憶化搜索進一步去梳理了依賴的關系，從簡單位置，通過這個依賴關系，算出復雜位置，進而求出所有表的過程。

網上大多數的博客/題解，上來就給你貼一個狀態轉移方程，然后根據這個狀態轉移方程去重新編一個故事作為解釋，你看了之后覺得挺有道理。但實際上，這個新編的故事是用結論去推原因，所以無論它講的多么清晰，多么有道理，它都已經脫離了原有的思維軌跡了。然后你就會看到評論區一片苦海，有人說“我知道應該dp但是不知道怎么dp”，“怎么才能想到狀態轉移方程啊”，“方法很巧但是自己想不出來”之類的，你想，為什么啊？作者已經擦掉了所有的思維軌跡，只留下最后的結論以及中間簡單的推理步驟，給你看到的證明都是特別漂亮的樣子，然后被認為是外星人留在地球的遺孤，我等凡人只能膜拜。你留下這些結論有什么用呢，你把那些思維過程都寫出來不是更加激勵后人嗎？所以等以后有一天，你成為高手了，請你對新手好一點。。

題解

class Solution {public int maxProfit(int[] prices) {// Solution 0：暴力遞歸+不合理的參數設計(TLE) // return process0(prices, 0, 2, -1, false);// Solution 1：暴力遞歸+刪除方法0中的start參數(TLE) // return process1(prices, 0, 2, false);// Solution 2：傻緩存(AC)// 注: 若用HashMap<int[3], Integer>做緩存, TLE // int[][][] dp = new int[prices.length + 1][3][2]; // for (int i = 0; i < dp.length - 1; i++) { // for (int j = 0; j < dp[0].length; j++) { // for (int k = 0; k < dp[0][0].length; k++) { // dp[i][j][k] = -1; // } // } // } // return process2(prices, 0, 2, 0, dp);// Solution 3: DP (AC)int[][][] dp = new int[prices.length + 1][3][2]; // i,count,pendingfor (int i = 0; i < dp.length - 1; i++) {for (int j = 0; j < dp[0].length; j++) {for (int k = 0; k < dp[0][0].length; k++) {dp[i][j][k] = -1;}}}for (int i = prices.length - 1; i >= 0; i--) {for (int pending = 0; pending < 2; pending++) {for (int count = 0; count < 3; count++) {if (pending == 0) {if (count == 0) {dp[i][count][pending] = 0;} else {int p1 = dp[i + 1][count][0];int p2 = -prices[i] + dp[i + 1][count - 1][1];dp[i][count][pending] = Math.max(p1, p2);}} else {int p1 = prices[i] + dp[i + 1][count][0];int p2 = dp[i + 1][count][1];dp[i][count][pending] = Math.max(p1, p2);}}}}return dp[0][2][0];}// public int process2(int[] prices, int i, int count, int pending, int[][][] dp) { // pending參數含義: 0-false 1-true // if (dp[i][count][pending] >= 0) return dp[i][count][pending]; // // if (pending == 0) { // 當前交易已關閉 // if (count == 0) { // 無法開啟新交易 // dp[i][count][pending] = 0; // return 0; // } else { // 可以開啟新交易 // int p1 = process2(prices, i + 1, count, 0, dp);// 持幣觀望 // int p2 = -prices[i] + process2(prices, i + 1, count - 1, 1, dp); // 開啟新交易 // dp[i][count][pending] = Math.max(p1, p2); // return dp[i][count][pending]; // } // } else { // 當前交易進行中 // int p1 = prices[i] + process2(prices, i + 1, count, 0, dp); // 結束當前交易，且i+1表示不立刻買入（立刻買入與持股觀望獲利相同，還浪費一次交易，沒必要） // int p2 = process2(prices, i + 1, count, 1, dp); // 持股觀望 // // dp[i][count][pending] = Math.max(p1, p2); // return dp[i][count][pending]; // } // } // // // 賣出是賺到的錢，買入是花費的錢，而非直接計算利潤 // public int process1(int[] prices, int i, int count, boolean pending) { // if (i == prices.length) return 0; // // if (!pending) { // 當前交易已關閉 // if (count == 0) { // 無法開啟新交易 // return 0; // } else { // 可以開啟新交易 // int p1 = process1(prices, i + 1, count, false);// 持幣觀望 // int p2 = -prices[i] + process1(prices, i + 1, count - 1, true); // 開啟新交易 // return Math.max(p1, p2); // } // } else { // 當前交易進行中 // int p1 = prices[i] + process1(prices, i + 1, count, false); // 結束當前交易，且i+1表示不立刻買入（立刻買入與持股觀望獲利相同，還浪費一次交易，沒必要） // int p2 = process1(prices, i + 1, count, true); // 持股觀望 // return Math.max(p1, p2); // } // } // // // 從當前位置i開始，已持有股票的買入價格為start，剩余count次交易的情況下，能獲得的最大profit // public int process0(int[] prices, int i, int count, int start, boolean pending) { // if (i == prices.length) return 0; // // if (!pending) { // 當前交易已關閉 // if (count == 0) { // 無法開啟新交易 // return 0; // } else { // 可以開啟新交易 // int p1 = process0(prices, i + 1, count, -1, false);// 持幣觀望 // int p2 = process0(prices, i + 1, count - 1, prices[i], true); // 開啟新交易 // return Math.max(p1, p2); // } // } else { // 當前交易進行中 // int p1 = (prices[i] - start) + process0(prices, i + 1, count, -1, false); // 結束當前交易，且i+1表示不立刻買入（立刻買入與持股觀望獲利相同，還浪費一次交易，沒必要） // int p2 = process0(prices, i + 1, count, start, true); // 持股觀望 // return Math.max(p1, p2); // } // } }

總結

以上是生活随笔為你收集整理的leetcode 123. Best Time to Buy and Sell Stock III | 123. 买卖股票的最佳时机 III（总结DP 模型套路）的全部內容，希望文章能夠幫你解決所遇到的問題。

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