算法训练营第三十九天（8.30）| 动态规划Part09：购买股票

 Leecode 123.买卖股票的最佳时机 III

题目地址：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目类型：股票问题

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();// dp[i][j]代表在第i的状态为j// j取值：0还没买过股票，1持有第一只股票，2卖出第一支股票，3持有第二支股票，4卖出第二支股票vector<vector<int>> dp(n, vector<int>(5));dp[0][1] = -prices[0];dp[0][3] = -prices[0];for (int i = 1; i < n; ++i) {dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]);dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3]);dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]);}return dp[n - 1][4];}
};

 Leecode 188.买卖股票的最佳时机 IV

题目地址：​​​​​​​力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目类型：股票问题

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2 * k + 1, 0));for (int i = 1; i < 2 * k; i += 2) {dp[0][i] = -prices[0]; }for (int i = 1; i < n; ++i) {for (int j = 1; j < 2 * k; j += 2) {dp[i][j] = max(dp[i - 1][j - 1] - prices[i], dp[i - 1][j]);dp[i][j + 1] = max(dp[i - 1][j] + prices[i], dp[i - 1][j + 1]);}}return dp[n - 1][2 * k];}
};