leetcode刷题
买卖股票的最佳时机III
其实类似，只是dp数组的状态又多了几种情况而已。
（本来我自己的想法是设置数组的长度是3，代表不持有，第一次持有，第二次持有，还有尝试不知道对不对）
int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int> (5));dp[0][0] = 0;dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];dp[0][4] = 0;for(int i = 1; i < prices.size(); i++){dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}return max(max(dp[prices.size() - 1][2], dp[prices.size() - 1][0]), dp[prices.size() - 1][4]);}买卖股票的最佳时机IV
和上一题差不多，进一步扩充了数组的维度而已。
int maxProfit(int k, vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int> (2*k + 1));for(int i = 0; i < 2*k + 1; i++){if(i % 2 == 0){dp[0][i] = 0;}else{dp[0][i] = -prices[0];}}for(int i = 1; i < prices.size(); i++){for(int j = 1; j <= 2*k; j++){if(j % 2 == 1){dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);}else{dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);}}}int result = dp[prices.size() - 1][1];for(int j = 1; j <= 2*k; j++){if(dp[prices.size() - 1][j] >= result)result = dp[prices.size() - 1][j];}return result;}