123.买卖股票的最佳时机III
题目链接/文章讲解/视频讲解:代码随想录
1.代码展现
- //123.买卖股票的最佳时机
- int maxProfit(vector<int>& prices) {
- if (prices.size() == 1) {
- return 0;
- }
- //step1 构建dp数组
- vector
int>> dp(prices.size(), vector<int>(5, 0)); - //dp[i][0]的含义是
- //dp[i][1]的含义是第一次持有股票的最大金额数
- //dp[i][2]的含义是第一次未持有(卖掉了)股票的最大金额数
- //dp[i][3]的含义是第二次持有股票的最大金额数
- //dp[i][4]的含义是第二次未持有(卖掉了)股票的最大金额数
- //step2 状态转移方程
- //dp[i][1] = max(dp[i - 1][1], -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])
- //step3 初始化dp数组
- dp[0][1] = -prices[0];
- dp[0][3] = -prices[0];
- //step4 开始遍历
- for (int i = 1; i < prices.size(); i++) {
- dp[i][1] = max(dp[i - 1][1], -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[prices.size() - 1][4];
-
- }
2.本题小节
思考:本题与昨天的题目不同点在于可以购买两次,因此第i天一共有四种状态,第一次持有,第一次未持有,第二次持有,第二次未持有,每次都有对应的状态转移公式,第一次持有的话,两种情况,前一天的,或者是当天买的;第一次未持有,要么就是前一天未持有,或者是今天卖的,是前一天持有的金钱加上卖票的金钱,第二次持有的同理。同时注意每一次持有的初始化,即-price[0]。
基本思路:明确状态转移公式和初始化。
188.买卖股票的最佳时机IV
题目链接/文章讲解/视频讲解:代码随想录
1.本题小节
- //188 买卖股票的最佳时机
- int maxProfit(int k, vector<int>& prices) {
- if (prices.size() == 1) {
- return 0;
- }
- //step1 构建dp数组
- vector
int>> dp(prices.size(), vector<int>(2 * k + 1, 0)); - //step2 状态转移方程
- //step3 初始化
- for (int j = 0; j < 2 * k; j += 2) {
- dp[0][j + 1] = -prices[0];
- }
- //step4 开始遍历
- for (int i = 1; i < prices.size(); i++) {
- for (int j = 0; j < 2 * k; j += 2)
- {
- //持有股票
- dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
- //未持有股票
- dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
-
- }
- }
- return dp[prices.size() - 1][2 * k];
- }
2.本题小节
思考:本题是可以买卖k次,通过上一题可以找到规律,主要是明确状态转移公式,要对1-k次依次创建状态转移公式,每天k次的状态都是持有和不持有两种,因此状态转移方程共有2k个,但是每次的的两种情况规律是一样的,每次持有的状态是两种情况,前一天的持有状态,或者是前一天未持有的状态减去prices[i];未持有的状态也是两种情况,前一天未持有的状态,或者是今天卖出股票的状态。注意初始化和上一题一样,但是有k次初始化,需要for循环遍历。
基本思路:明确状态转移公式和初始化。