代码随想录算法训练营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];
}
};

原文地址：https://blog.csdn.net/qq_56445436/article/details/142642123

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！