LC：动态规划-买卖股票

121. 买卖股票的最佳时机

链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

使用贪心，直接秒了，需要注意的是，由于题目所说股票只能购买一次，所以不存在累加的情况，对比下面第二题思考：
代码：

class Solution {public int maxProfit(int[] prices) {// 只能有一直股票，所以价格不能够累加，只拥有一直股票。int minPrice = prices[0];int ans = 0;for(int price : prices){ans = Math.max(ans, price - minPrice);minPrice = Math.min(minPrice, price);}return ans;}
}

122. 买卖股票的最佳时机 II

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

方法一：直接使用贪心，类似第一题，本题最大不同在于可以多次购买并且出售股票，只需要保证每次购买后出售股票中获取利润大于0即可，随后将遍历过程中获取到的所有利润相加，并且需要及时更新上次购买股票的价格：prevPrice即可。
代码如下：

class Solution {public int maxProfit(int[] prices) {// 直接贪心int ans = 0;int prevPrice = prices[0];for(int price : prices){if(price - prevPrice > 0){ans += price - prevPrice;}prevPrice = price;}return ans;}
}

方法二：动态规划 秒了，设二维dp数组，dp[i][0]表示第i天不持有能够获得的最大利润，dp[i][1]表示第 i 天持有股票能够获取的最大利润。
注意需要初始化第一天的利润值：dp[0][0] = 0，dp[0][1] = -prices[0]；
具体动态数组递推公式参考下面代码：

class Solution {public int maxProfit(int[] prices) {// 动态规划,dp[i][0]表示第i天不持有股票能够获取的最大利润，dp[i][1]表示第i天持有股票能够获取的最大利润int m = prices.length;int[][] dp = new int[m][2];dp[0][0] = 0; dp[0][1] = -prices[0];for(int i = 1; i < m; 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 Math.max(dp[m - 1][0], dp[m - 1][1]);}
}

对于动态规划的理解，是解决下面变形题的关键。

714. 买卖股票的最佳时机含手续费

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

带手续费的题目本质上和上面题目使用动态规划解决并无差异。
首先需要明确题目意思，题目说道，每笔交易需要支付一笔手续费，并且这个手续费指的是买入、卖出这整个过程。 借助此，我们可以将手续费统一到购买股票的时候支付，此后题目就和上述动态规划一样。
代码如下：

class Solution {public int maxProfit(int[] prices, int fee) {// 动态规划// dp[i][0]表示第i天不持有股票能够获取的最大利润// dp[i][1]表示第i天持有股票能够获取的最大利润// 并且规定股票的手续费全部在买入的时候付，卖出的时候不需要付手续费int len = prices.length;int[][] dp = new int[len][2];dp[0][0] = 0;dp[0][1] = -prices[0] - fee;for(int i = 1; i < len; 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] - fee);}return Math.max(dp[len - 1][0], dp[len - 1][1]);}
}

309. 买卖股票的最佳时机含冷冻期

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

第一次看到题目联想到的是在上面两道动态规划的基础上修改一番，仍然使用两个变量表示0表示不持有股票，1表示持有股票。但此时存在一个问题：对于dp[i][0] 不持有股票的表示，无法确定对于某一天「是前一天不持有股票还是前一天持有股票随后将股票卖掉而出现的新的不持有股票的状态。」对于这两种不同的状态采用的处理方式也不同，所以使用两种状态进行动态规划存在状态歧义。意识到这一点后，在两个状态变量的基础上添加新的一个新的状态。此时使用dp[len][3]进行递归。

• dp[i][0]：表示第i天不持有股票且未卖出股票。
• dp[i][1]：表示第i天不持有股票且可能有卖出股票。
• dp[i][2]：表示第i天持有股票。

具体状态转移公式及参考下面代码：

class Solution {public int maxProfit(int[] prices) {// 动态规划int len = prices.length;int[][] dp = new int[len][3];// dp[i][0]不持有未卖出 dp[i][1]不持有有卖出 dp[i][2]持有dp[0][0] = 0;dp[0][1] = 0;dp[0][2] = -prices[0];for(int i = 1; i < len; i++){dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] + prices[i]);dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][0] - prices[i]);}return Math.max(dp[len - 1][0], Math.max(dp[len - 1][1], dp[len - 1][2]));}
}