网站开发前景与趋势如何,哪家公司建设网站好,网站建设与管理课后答案,便宜域名309.最佳买卖股票时机含冷冻期 关键点1#xff1a;dp数组的含义
1-1#xff1a;dp[i][0] 第i天持有股票的最大金钱 1-2#xff1a;dp[i][1] 第i天卖出股票的最大金钱 1-3#xff1a;dp[i][2] 第i天处于冷冻期的最大金钱 1-4#xff1a;dp[i][3] 第i天保持卖出股票的最大金… 309.最佳买卖股票时机含冷冻期 关键点1dp数组的含义
1-1dp[i][0] 第i天持有股票的最大金钱 1-2dp[i][1] 第i天卖出股票的最大金钱 1-3dp[i][2] 第i天处于冷冻期的最大金钱 1-4dp[i][3] 第i天保持卖出股票的最大金钱
关键点2递归公式的推导
2-1dp[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-2dp[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天处于冷冻期的最大金钱)
关键点3dp数组初始化
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.买卖股票的最佳时机含手续费 关键点1dp数组的含义
1-1dp[i][0] 第i天不持有股票的最大金钱 1-2dp[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-2dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]-prices[i]); 第i天持有股票的最大金钱 max(第i-1天持有股票的最大金钱第i-1天不持有股票-第i天买入股票的最大金钱)
关键点3dp数组初始化
dp[0][0] 0dp[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];}
}
