腾讯网站建设推广站长之家排名查询
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];}
}