算法訓(xùn)練營 day52 動態(tài)規(guī)劃 買賣股票的最佳時機(jī)系列1

買賣股票的最佳時機(jī)

121. 買賣股票的最佳時機(jī) - 力扣（LeetCode）

給定一個數(shù)組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設(shè)計(jì)一個算法來計(jì)算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

   dp[i][0] 表示第i天持有股票所得最多現(xiàn)金 ，dp[i][1] 表示第i天不持有股票所得最多現(xiàn)金

2. 確定遞推公式

   如果第i天持有股票即dp[i][0]， 那么可以由兩個狀態(tài)推出來

   • 第i-1天就持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天持有股票的所得現(xiàn)金 即：dp[i - 1][0]
   • 第i天買入股票，所得現(xiàn)金就是買入今天的股票后所得現(xiàn)金即：-prices[i]

   那么dp[i][0]應(yīng)該選所得現(xiàn)金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

   如果第i天不持有股票即dp[i][1]， 也可以由兩個狀態(tài)推出來

   • 第i-1天就不持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 即：dp[i - 1][1]
   • 第i天賣出股票，所得現(xiàn)金就是按照今天股票價格賣出后所得現(xiàn)金即：prices[i] + dp[i - 1][0]

   同樣dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

3. dp數(shù)組如何初始化

   由遞推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出其基礎(chǔ)都是要從dp[0][0]和dp[0][1]推導(dǎo)出來。

   那么dp[0][0]表示第0天持有股票，此時的持有股票就一定是買入股票了，因?yàn)椴豢赡苡星耙惶焱瞥鰜?#xff0c;所以dp[0][0] -= prices[0];

   dp[0][1]表示第0天不持有股票，不持有股票那么現(xiàn)金就是0，所以dp[0][1] = 0;

4. 確定遍歷順序

   從遞推公式可以看出dp[i]都是由dp[i - 1]推導(dǎo)出來的，那么一定是從前向后遍歷。

5. 舉例推導(dǎo)dp數(shù)組

以示例1，輸入：[7,1,5,3,6,4]為例，dp數(shù)組狀態(tài)如下：

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

買賣股票的最佳時機(jī)II

122. 買賣股票的最佳時機(jī) II - 力扣（LeetCode）

給你一個整數(shù)數(shù)組 prices ，其中 prices[i] 表示某支股票第 i 天的價格。

在每一天，你可以決定是否購買和/或出售股票。你在任何時候 最多 只能持有 一股 股票。你也可以先購買，然后在 同一天 出售。

返回 你能獲得的 最大 利潤 。

如果第i天持有股票即dp[i][0]， 那么可以由兩個狀態(tài)推出來

• 第i-1天就持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天持有股票的所得現(xiàn)金 即：dp[i - 1][0]
• 第i天買入股票，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金減去今天的股票價格 即：dp[i - 1][1] - prices[i]

注意這里和121. 買賣股票的最佳時機(jī)唯一不同的地方，就是推導(dǎo)dp[i][0]的時候，第i天買入股票的情況。

在121. 買賣股票的最佳時機(jī)中，因?yàn)楣善比讨荒苜I賣一次，所以如果買入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]。

而本題，因?yàn)橐恢还善笨梢再I賣多次，所以當(dāng)?shù)趇天買入股票的時候，所持有的現(xiàn)金可能有之前買賣過的利潤。

那么第i天持有股票即dp[i][0]，如果是第i天買入股票，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 減去 今天的股票價格 即：dp[i - 1][1] - prices[i]。

再來看看如果第i天不持有股票即dp[i][1]的情況， 依然可以由兩個狀態(tài)推出來

• 第i-1天就不持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 即：dp[i - 1][1]
• 第i天賣出股票，所得現(xiàn)金就是按照今天股票價格賣出后所得現(xiàn)金即：prices[i] + dp[i - 1][0]

class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][2];dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < prices.length; 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[prices.length-1][1];}
}