腾讯网站建设推广品牌策划公司哪家好

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];}
}