代码随想录算法训练营day41

1.买卖股票的最佳时机

1.1 题目

. - 力扣（LeetCode）

1.2 题解

class Solution {
public:int maxProfit(vector<int>& prices){//定义dp数组，dp[i][0]表示第i天不持有股票身上的现金，dp[i][1]表示第i天持有股票身上的现金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++){dp[i][0]=max(dp[i-1][0],dp[i-1][1] + prices[i]);dp[i][1]=max(dp[i-1][1],-prices[i]);}return dp[prices.size()-1][0];}
};

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

2.1 题目

. - 力扣（LeetCode）

2.2 题解

class Solution
{
public:int maxProfit(vector<int>& prices){//确定dp数组，dp[i][0]表示第i天手上没有股票身上的钱，dp[i][1]表示第i天有股票身上的钱vector<vector<int>> dp(prices.size(), vector<int>(2, 0));//确定递推公式// dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);// dp[i][1] = max(dp[i - 1][1], dp[i-1][0]-prices[i]);//初始化dp[0][0] = 0;dp[0][1] = -prices[0];//开始遍历for (int i = 1; i < prices.size(); i++){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i-1][0]-prices[i]);}return dp[prices.size() - 1][0];}
};

3.买卖股票的最佳时机

3.1 题目

. - 力扣（LeetCode）

3.2 题解

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();//定义dp数组vector<vector<int>> dp(len, vector<int>(5, 0));//dp数组有5个状态//dp[i][0]表示第i天不进行操作//dp[i][1]表示第i天第一次持有股票//dp[i][2]表示第i天第一次不持有股票//dp[i][3]表示第i天第二次持有股票//dp[i][4]表示第i天第二次不持有股票//确定递推逻辑/*dp[i][0] = dp[i - 1][0];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]);*///初始化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 < len; i++){dp[i][0] = dp[i - 1][0];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 dp[len - 1][4];}
};