代码随想录算法训练营第四十八天|121. 买卖股票的最佳时机，122.买卖股票的最佳时机II

本文主要是介绍代码随想录算法训练营第四十八天|121. 买卖股票的最佳时机，122.买卖股票的最佳时机II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

121. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机

文档讲解：代码随想录

视频讲解：动态规划之 LeetCode：121.买卖股票的最佳时机1

思路

采用二维dp数组，dp[i][0]表示第i天交易完成后手里没有股票的最大利润，dp[i][1]表示第i天交易完后手里有一支股票的最大利润。

递推公式：dp[i][0]可有两种状态推出，两者取最大值

前一天手里本来就没有股票，即dp[i - 1][0]
前一天手里有一支股票，但是在第i天卖出，即dp[i - 1][1] + price[i]

dp[i][1]也可以由两种状态推出，两者取最大值

前一天手里本来就有一支股票，即dp[i - 1][1]
前一天手里没有股票，但是在第i天买入一支股票，即-price[i]，因为只能买一支股票，所以买入股票后的利润为-price[i]，不能在前一天的基础上-price[i]

代码

class Solution {
public:// dp[i][0]表示第i天不持有股票所得最多现金// dp[i][1]表示第i天持有股票所得最多现金int maxProfit(vector<int> &prices) {vector<vector<int>> dp(prices.size(), vector<int>(2, 0));dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < prices.size(); i++) {// 第i天不持有股票，可从两个状态推出// 1. 第i-1天就不持有股票// 2. 第i-1天持有股票，在第i天卖出dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);// 第i天持有股票，可以从两个状态推出// 1. 第i-1天就持有股票// 2. 第i-1天不持有股票，在第i天买入股票dp[i][1] = max(dp[i - 1][1], -prices[i]);}return dp[prices.size() - 1][0];}
};

122.买卖股票的最佳时机II

题目链接：122.买卖股票的最佳时机II

文档讲解：代码随想录

视频讲解：动态规划，股票问题第二弹 | LeetCode：122.买卖股票的最佳时机II

思路

与上一题类似，但是在计算dp[i][1]时，前一天没有股票，在第i天买入一支股票，为dp[i - 1][0] - price[i]，即在前一天没有股票的最大利润基础上买入股票。

代码

class Solution {
public:// dp[i][0]表示第i天不持有股票所得最多现金// dp[i][1]表示第i天持有股票所得最多现金int maxProfit(vector<int> &prices) {vector<vector<int>> dp(prices.size(), vector<int>(2, 0));dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < prices.size(); i++) {// 第i天不持有股票，可从两个状态推出// 1. 第i-1天就不持有股票// 2. 第i-1天持有股票，在第i天卖出dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);// 第i天持有股票，可以从两个状态推出// 1. 第i-1天就持有股票// 2. 第i-1天不持有股票，在第i天买入股票（因为能多次买卖股票，所以当天买入股票时的现金为前一天不持有股票的现金）dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[prices.size() - 1][0];}
};