【代码随想录】day50

2024-05-04 15:44

文章标签 随想录代码 day50

本文主要是介绍【代码随想录】day50，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

一、123买卖股票的最佳时机III
二、188买卖股票的最佳时机IV

一、123买卖股票的最佳时机III

超时了。。。

class Solution {
public:int helper(vector<int>& prices, int start, int end) {int profit = 0;int buyPrice = prices[start];for (int i = start + 1; i < end; i ++) {profit = max(profit, prices[i] - buyPrice);buyPrice = min(buyPrice, prices[i]);}return profit;}int maxProfit(vector<int>& prices) {int result = 0;for (int i = 1; i < prices.size(); i ++) {if (prices[i] <= prices[i-1]) {continue;}result = max(result, helper(prices, 0, i) + helper(prices, i - 1, prices.size()));}return result;}
};

二维dp：

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(5, 0));dp[0][1] = -prices[0];dp[0][3] = -prices[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]);}// for (auto vec: dp) {//     for (int num: vec) cout << num << " ";//     cout << endl;// }return dp[prices.size()-1][4];}
};

二、188买卖股票的最佳时机IV

上一道题举一反三即可，但上一道题的二维dp真滴想不到呀。。

class Solution {
public:int maxProfit(int k, vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(1 + 2 * k, 0));for (int i = 1; i < dp[0].size(); i += 2) {dp[0][i] = -prices[0];}for (int i = 1; i < prices.size(); i ++) {for (int j = 1; j < dp[0].size(); 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]);}}}// for (auto vec: dp) {//     for (int num: vec) cout << num << " ";//     cout << endl;// }return dp[prices.size() - 1][2 * k];}
};