代码随想录算法训练营第四十一天 | 121-买卖股票的最佳时机、122-买卖股票的最佳时机Ⅱ、123-买卖股票的最佳时机Ⅲ
LeetCode121 买卖股票的最佳时机
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
文章讲解：https://programmercarl.com/0121.买卖股票的最佳时机.html
视频讲解：
动规五部曲：
- 确定dp数组以及下标的含义
dp[i][0]表示在第i天持有股票所得最多现金（初始现金为0，买入股票后为负数）
dp[i][1]表示在第i天不持有股票所得最多现金
- 确定递推公式
如果第i天持有股票即dp[i][0]，那么它可由两个状态推出：
- 第 i-1 天就已持有股票，保持现状，dp[i][0] = dp[i-1][0]
- 第 i 天买入股票，dp[i][0] = -prices[i]
如果第i天未持有股票即dp[i][1]，那么它可由两个状态推出：
-
第 i-1 天未持有股票，dp[i][1] = dp[i-1][1]
-
第 i 天卖出股票，dp[i][1] = dp[i-1][0] + prices[i]
由此得到状态转移方程：
dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
从该递推公式可看出，dp[i]只依赖于dp[i-1]，因此可以使用滚动数组将二维dp进行压缩
dp[i%2][0] = Math.max(dp[(i-1)%2][0], -prices[i]);
dp[i%2][1] = Math.max(dp[(i-1)%2][1], dp[(i-1)%2][0] + prices[i]);
- dp数组如何初始化
dp[0][0] = -prices[0]，第零天持有股票，那么就肯定是第零天买入了股票
dp[0][1] = 0，第零天未持有股票，那么就肯定是第零天未买入股票，维持初始现金0
- 确定遍历顺序
由递推公式得出，从1开始往后顺序遍历
- 举例推导dp数组
class Solution {public int maxProfit(int[] prices) {if(prices.length == 1){return 0;}int[][] dp = new int[2][2];dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < prices.length; i++){dp[i%2][0] = Math.max(dp[(i-1)%2][0], -prices[i]);dp[i%2][1] = Math.max(dp[(i-1)%2][1], dp[(i-1)%2][0] + prices[i]);}return dp[(prices.length-1)%2][1];}
}
LeetCode122 买卖股票的最佳时机Ⅱ
题目链接：
文章讲解：https://programmercarl.com/0122.买卖股票的最佳时机II（动态规划）.html
视频讲解：https://www.bilibili.com/video/BV1D24y1Q7Ls/?vd_source=b989f2b109eb3b17e8178154a7de7a51
动规五部曲：
- 确定dp数组以及下标的含义
dp[i][0]表示在第i天持有股票所得最多现金（初始现金为0，买入股票后为负数）
dp[i][1]表示在第i天不持有股票所得最多现金
- 确定递推公式
如果第i天持有股票即dp[i][0]，那么它可由两个状态推出：
- 第 i-1 天就已持有股票，保持现状，dp[i][0] = dp[i-1][0]
- 第 i 天买入股票，所得现金就是昨日未持有-今日股价，dp[i][0] = dp[i-1][1] - prices[i]
如果第i天未持有股票即dp[i][1]，那么它可由两个状态推出：
-
第 i-1 天未持有股票，dp[i][1] = dp[i-1][1]
-
第 i 天卖出股票，所得现金就是昨日持有+今日股价，dp[i][1] = dp[i-1][0] + prices[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]);
从该递推公式可看出，dp[i]只依赖于dp[i-1]，因此可以使用滚动数组将二维dp进行压缩
dp[i%2][0] = Math.max(dp[(i-1)%2][0], dp[(i-1)%2][1] - prices[i]);
dp[i%2][1] = Math.max(dp[(i-1)%2][1], dp[(i-1)%2][0] + prices[i]);
- dp数组如何初始化
dp[0][0] = -prices[0]，第零天持有股票，那么就肯定是第零天买入了股票
dp[0][1] = 0，第零天未持有股票，那么就肯定是第零天未买入股票，维持初始现金0
- 确定遍历顺序
由递推公式得出，从1开始往后顺序遍历
- 举例推导dp数组
class Solution {public int maxProfit(int[] prices) {if(prices.length == 1){return 0;}int[][] dp = new int[2][2];dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < prices.length; i++){dp[i%2][0] = Math.max(dp[(i-1)%2][0], dp[(i-1)%2][1] - prices[i]);dp[i%2][1] = Math.max(dp[(i-1)%2][1], dp[(i-1)%2][0] + prices[i]);}return dp[(prices.length-1)%2][1];}
}
LeetCode123 买卖股票的最佳时机Ⅲ
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
文章讲解：https://programmercarl.com/0123.买卖股票的最佳时机III.html
视频讲解：https://www.bilibili.com/video/BV1WG411K7AR/
动规五部曲：
- 确定dp数组以及下标的含义
dp[i][0]表示第i天不操作所得最大现金
dp[i][1]表示第i天第一次持有股票所得最大现金
dp[i][2]表示第i天第一次不持有股票所得最大现金
dp[i][3]表示第i天第二次持有股票所得最大现金
dp[i][4]表示第i天第二次不持有股票所得最大现金
- 确定递推公式
dp[i][0] = dp[i-1][0]，第i天不操作，保持前一天的状态
dp[i][1] = Math.max(dp[i-1][1]，dp[i-1][0] - prices[i])，之前已经买入，延续前一天的结果；第i天买入股票
dp[i][2] = Math.max(dp[i-1][2]，dp[i-1][1] + prices[i])，前一天就已是不持有的状态，延续前一天结果/第i天卖出股票
dp[i][3] = Math.max(dp[i-1][3]，dp[i-1][2] - prices[i])，之前已经买入，延续前一天的结果；第i天买入股票
dp[i][4] = Math.max(dp[i-1][4]，dp[i-1][3] + prices[i])，前一天就已是不持有的状态，延续前一天结果/第i天卖出股票
整理得状态转移方程：
dp[i][0] = dp[i-1][0];
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);
dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);
由递推公式可以看出，dp[i]只依赖于dp[i-1]，那么可以用滚动数组将二维dp压缩：
dp[i%2][0] = dp[(i-1)%2][0];
dp[i%2][1] = Math.max(dp[(i-1)%2][1], dp[(i-1)%2][0] - prices[i]);
dp[i%2][2] = Math.max(dp[(i-1)%2][2], dp[(i-1)%2][1] + prices[i]);
dp[i%2][3] = Math.max(dp[(i-1)%2][3], dp[(i-1)%2][2] - prices[i]);
dp[i%2][4] = Math.max(dp[(i-1)%2][4], dp[(i-1)%2][3] + prices[i]);
- dp数组如何初始化
dp[0][0] = 0
dp[0][1] = -prices[0]、dp[0][3] = -prices[0]
dp[0][2] = 0、dp[0][4] = 0
- 确定遍历顺序
由递推公式得出，从1开始往后顺序遍历
- 举例推导dp数组
class Solution {public int maxProfit(int[] prices) {if(prices.length == 1){return 0;}int[][] dp = new int[2][5];dp[0][0] = 0;dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];dp[0][4] = 0;for(int i = 1; i < prices.length; i++){dp[i%2][0] = dp[(i-1)%2][0];dp[i%2][1] = Math.max(dp[(i-1)%2][1], dp[(i-1)%2][0] - prices[i]);dp[i%2][2] = Math.max(dp[(i-1)%2][2], dp[(i-1)%2][1] + prices[i]);dp[i%2][3] = Math.max(dp[(i-1)%2][3], dp[(i-1)%2][2] - prices[i]);dp[i%2][4] = Math.max(dp[(i-1)%2][4], dp[(i-1)%2][3] + prices[i]);}return dp[(prices.length-1)%2][4];}
}