代码随想录打卡第51天|309.最佳买卖股票时机含冷冻期；714.买卖股票的最佳时机含手续费
309.最佳买卖股票时机含冷冻期
关键点1：dp数组的含义
1-1：dp[i][0] 第i天持有股票的最大金钱
1-2：dp[i][1] 第i天卖出股票的最大金钱
1-3：dp[i][2] 第i天处于冷冻期的最大金钱
1-4：dp[i][3] 第i天保持卖出股票的最大金钱
关键点2：递归公式的推导
2-1：dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][3]-prices[i],dp[i-1][2] - prices[i])); 第i天持有股票的最大金钱 = max( 第i-1天持有股票的最大金钱，第i-1天保持卖出股票的最大金钱-买入股票的金钱 ,前一天是冷冻期-买入股票的金钱)
2-2：dp[i][1] = dp[i-1][0]+prices[i]; 第i天卖出股票的最大金钱 = 第i-1天持有股票的最大金钱+卖出股票的金钱
2-3： dp[i][2] = dp[i-1][1]; 第i天处于冷冻期的最大金钱 = 第i-1天处于卖出的最大金钱
2-4： dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]); 第i天保持卖出股票的最大金钱 = max( 第i-1天保持卖出股票的最大金钱，第i-1天处于冷冻期的最大金钱)
关键点3：dp数组初始化
dp[0][0] = - prices[0] ，dp[0][1] =0， dp[0][2] = 0， dp[0][3] = 0;
关键点4：遍历顺序
由于下一个dp值与上一个dp值有关，因此for循环从前往后遍历（0已经初始化了，从1开始遍历）
class Solution {
public int maxProfit(int[] prices) {
// dp[i][0] 第i天持有股票的最大金钱
// dp[i][1] 第i天卖出股票的最大金钱
// dp[i][2] 第i天处于冷冻期的最大金钱
// dp[i][3] 第i天保持卖出股票的最大金钱
int[][] dp = new int[prices.length][4];
dp[0][0] = -prices[0];;
dp[0][1] = 0;
dp[0][2] = 0;
dp[0][3] = 0;
for(int i = 1;i < prices.length;i++){
// 第i-1天持有股票的最大金钱，第i-1天保持卖出股票的最大金钱-买入股票的金钱 ,前一天是冷冻期
dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][3]-prices[i],dp[i-1][2] - prices[i]));
// 第i-1天持有股票的最大金钱+卖出股票的金钱
dp[i][1] = dp[i-1][0]+prices[i];
// 第i-1天处于卖出的最大金钱
dp[i][2] = dp[i-1][1];
// 第i-1保持卖出股票的最大金钱,第i-1天处于冷冻期的最大金钱
dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]);
}
return Math.max(dp[prices.length-1][1], Math.max(dp[prices.length-1][2], dp[prices.length-1][3]));
}
}714.买卖股票的最佳时机含手续费
关键点1：dp数组的含义
1-1：dp[i][0] 第i天不持有股票的最大金钱
1-2：dp[i][1] 第i天持有股票的最大金钱
关键点2：递归公式的推导
2-1： dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee); 第i天不持有股票的最大金钱 = max(第i-1天不持有股票的最大金钱，第i-1天持有股票+第i天卖出股票的最大金钱-手续费)
2-2：dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]); 第i天持有股票的最大金钱 = max(第i-1天持有股票的最大金钱，第i-1天不持有股票-第i天买入股票的最大金钱)
关键点3：dp数组初始化
dp[0][0] = 0，dp[0][1] = - prices[0]
关键点4：遍历顺序
由于下一个dp值与上一个dp值有关，因此for循环从前往后遍历（0已经初始化了，从1开始遍历）
class Solution {
public int maxProfit(int[] prices, int fee) {
// dp[i][0] 第i天不持有股票的最大金钱
// dp[i][1] 第i天持有股票的最大金钱
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1;i < prices.length;i++){
// 第i天不持有股票的最大金钱 = max(第i-1天不持有股票的最大金钱，第i-1天持有股票+第i天卖出股票的最大金钱-手续费)
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
// 第i天持有股票的最大金钱 = max(第i-1天持有股票的最大金钱，第i-1天不持有股票-第i天买入股票的最大金钱)
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[prices.length-1][0];
}
}