网站建设技术方案,网站官网,建站高端网站,商贸行业网站建设公司309.最佳买卖股票时机含冷冻期 1. 确定dp数组#xff08;dp table#xff09;以及下标的含义 dp[i][j]#xff0c;第i天状态为j#xff0c;所剩的最多现金为dp[i][j]。 2. 确定递推公式 拆分卖出股票状态是因为冷冻期前一天一定是具体卖出股票状态。 状态一 dp[i][0]… 309.最佳买卖股票时机含冷冻期 1. 确定dp数组dp table以及下标的含义 dp[i][j]第i天状态为j所剩的最多现金为dp[i][j]。 2. 确定递推公式 拆分卖出股票状态是因为冷冻期前一天一定是具体卖出股票状态。 状态一 dp[i][0]持有股票状态今天买入股票或者是之前就买入了股票然后没有操作一直持有 dp[i-1][0] dp[i-1][3] - prices[i]冷冻期后买入dp[i-1][1] - prices[i]买入前一天保持卖出股票状态 dp[i][0] max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]); 不持有股票状态这里就有两种卖出股票状态 状态二 dp[i][1]保持卖出股票的状态两天前就卖出了股票度过一天冷冻期。或者是前一天就是卖出股票状态一直没操作 dp[i-1][1] dp[i-1][3] dp[i][1] max(dp[i - 1][1], dp[i - 1][3]);状态三 dp[i][2]今天具体卖出股票前一天一定是持有股票状态才能卖 dp[i-1][0] prices[i] dp[i][2] dp[i - 1][0] prices[i]; 状态四 dp[i][3]今天为冷冻期状态但冷冻期状态不可持续只有一天 dp[i-1][2] 前一天为具体卖出股票状态 dp[i][3] dp[i - 1][2]; 3. dp数组如何初始化 如果是持有股票状态状态一那么dp[0][0] -prices[0]一定是当天买入股票。 dp[0][1] 由于状态本身为非法状态。我们看递推公式中需要把它初始化成多少就把它初始化成多少。 (1)用到了dp[0][1] dp[i][0] dp[i - 1][1] - prices[i]; (1) Subsitutde i1 into (1) dp[1][0] dp[0][1] - prices[1]; 第0天状态1初始化为0 dp[0][1] 初始化为0 让递推公式从第一天合理推导下去 同理dp[0][2] 0 dp[0][3] 0 // 第0天就是冷冻期状态不合法 4. 确定遍历顺序 从前往后遍历 for (int i 1; i prices.size(); i) { 持有股票的状态此时手头现金一定不是最大的。最后一天的状态1、2、3都有可能是最大值。 最后结果最后一天手头最大现金 max(dp[price.size()-1][1], dp[price.size()-1][2], dp[price.size()-1])[3]) 5. 举例推导dp数组 714.买卖股票的最佳时机含手续费
