代码随想录算法训练营第36期DAY52

本文主要是介绍代码随想录算法训练营第36期DAY52，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DAY52

123买卖股票的最佳时机iii

主要是想不到：每天有5个状态（无操作，第一次持有股票、第一次不持有股票、第二次持有股票、第二次不持有股票）

1. class Solution {
2. public:
3.     int maxProfit(vector<int>& prices) {
4.         vector<int> dp(5,0);
5.         dp[1]=-prices[0];
6.         dp[3]=-prices[0];
7.         for(int i=0;i<prices.size();i++){
8.             dp[1]=max(dp[1],dp[0]-prices[i]);
9.             dp[2]=max(dp[2],dp[1]+prices[i]);
10.             dp[3]=max(dp[3],dp[2]-prices[i]);
11.             dp[4]=max(dp[4],dp[3]+prices[i]);
12.         }
13.         return dp[4];
14.     }
15. };

188买卖股票的最佳时机iv

别忘了初始化

初始化错了，应该是price[0] 而不是price[i]，为什么呢：因为它是在第一天，用的第一天来初始化。

1. class Solution {
2. public:
3.     int maxProfit(int k, vector<int>& prices) {
4.         vector<int> dp(2 * k + 1, 0);
5.         // 别忘了初始化：
6.         for (int j = 1; j < 2 * k; j += 2) {
7.             dp[j] = -prices[0];
8.         }
9.         //初始化错了，应该是price[0]，为什么呢：因为它是在第一天，用的第一天来初始化。
10.         /* 错误：
11.         for (int i = 1; i < 2 * k; i += 2) {
12.             if (i % 2 != 0)
13.                 dp[i] = -1 * prices[i];
14.         }
15.         */
16.         for (int i = 0; i < prices.size(); i++) {
17.             for (int j = 1; j <= 2 * k; j++) {
18.                 if (j % 2 != 0)
19.                     dp[j] = max(dp[j], dp[j - 1] - prices[i]);
20.                 else
21.                     dp[j] = max(dp[j], dp[j - 1] + prices[i]);
22.             }
23.         }
24.         return dp[2 * k];
25.     }
26. };

这篇关于代码随想录算法训练营第36期DAY52的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---