赞
踩
力扣对应题目链接:188. 买卖股票的最佳时机 IV - 力扣(LeetCode)
牛客对应题目链接:买卖股票的最好时机(四)_牛客题霸_牛客网 (nowcoder.com)
为了更加清晰的区分买入和卖出,我们换成有股票和无股票两个状态。
- f[i][j] 表示:第 i 天结束后,完成了 j 笔交易,此时处于有股票状态的最大收益。
- g[i][j] 表示:第 i 天结束后,完成了 j 笔交易,此时处于无股票状态的最大收益。
对于 f[i][j],也有两种情况能在第 i 天结束之后,完成 j 笔交易,此时手里有股票的状态:
- 在 i-1 天的时候,手里有股票,并且交易了 j 次。在第 i 天的时候,啥也不干。此时的收益为 f[i - 1][j]。
- 在 i-1 天的时候,手里没有股票,并且交易了 j 次。在第 i 天的时候,买了股票。那么 i 天结束之后,就有股票了。此时的收益为 g[i - 1][j] - prices[i]。
上述两种情况,我们需要的是最大值,因此 f 的状态转移方程为:
f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]
对于 g[i][j],我们有下⾯两种情况能在第 i 天结束之后,完成 j 笔交易,此时手里没有股票的状态:
- 在 i-1 天的时候,手里没有股票,并且交易了 j 次。在第 i 天的时候,啥也不干。此时的收益为 g[i - 1][j]。
- 在 i-1 天的时候,手里有股票,并且交易了 j - 1 次。在第 i 天的时候,把股票卖了。那么 i 天结束之后,我们就交易了 j 次。此时的收益为 f[i - 1][j - 1] + prices[i]。
上述两种情况,我们需要的是最大值,因此 g 的状态转移方程为:
g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i])
它们之间交易关系如下:
从上往下填每一行,每一行从左往右,两个表⼀起填。
返回处于卖出状态的最大值,但是我们也不知道是交易了几次,因此返回 g 表最后一行的最大值。
我们的交易次数是不会超过整个天数的一半的,因此我们可以先把 k 处理一下,优化一下问题的规模:k = min(k, n / 2)。
- //力扣
- //【动态规划-二维dp-2个状态】
- class Solution {
- //f[i][j]:第i天结束后,完成了j次交易,此时处于“买入”状态下的最大利润
- //g[i][j]:第i天结束后,完成了j次交易,此时处于“卖出”状态下的最大利润
- private:
- const int INF=0x3f3f3f3f;
- public:
- int maxProfit(int k, vector<int>& prices) {
- int n=prices.size();
- k=min(k, n/2); //优化:处理最多交易次数
- vector<vector<int>> f(n, vector<int>(k+1, -INF));
- vector<vector<int>> g(n, vector<int>(k+1, -INF));
- f[0][0]=-prices[0], g[0][0]=0;
- for(int i=1; i<n; i++)
- {
- for(int j=0; j<=k; j++)
- {
- f[i][j]=max(f[i-1][j], g[i-1][j]-prices[i]);
- g[i][j]=g[i-1][j];
- if(j>=1) g[i][j]=max(g[i][j], f[i-1][j-1]+prices[i]);
- }
- }
- int res=0;
- for(int j=0; j<=k; j++)
- res=max(res, g[n-1][j]);
- return res;
- }
- };
-
- //【动态规划-二维dp-2k+1个状态】
- class Solution {
- //dp[i][0] -- 没有操作
- //下面j为奇数:买入;j为偶数:卖出 (j的范围:1~2k-1)
- //dp[i][j] -- 第1~k次买入
- //dp[i][j+1] -- 第1~k次卖出
- public:
- int maxProfit(int k, vector<int>& prices) {
- int n=prices.size();
- vector<vector<int>> dp(n, vector<int>(2*k+1));
- for(int j=1; j<2*k; j+=2)
- dp[0][j]=-prices[0];
- for(int i=1; i<n; 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[n-1][2*k];
- }
- };
- //牛客
- #include <iostream>
- #include <cstring>
- using namespace std;
-
- const int INF=0x3f3f3f3f;
- const int N=1010, M=110;
- int prices[N];
- int f[N][M], g[N][M];
- //f[i][j]:第i天结束后,完成了j次交易,此时处于“买入”状态下的最大利润
- //g[i][j]:第i天结束后,完成了j次交易,此时处于“卖出”状态下的最大利润
-
- int main()
- {
- int n, k;
- cin >> n >> k;
- for(int i=0; i<n; i++)
- cin >> prices[i];
- memset(f, -INF, sizeof(f));
- memset(g, -INF, sizeof(g));
- int res=0;
- f[0][0]=-prices[0], g[0][0]=0;
- for(int i=1; i<n; i++)
- {
- for(int j=0; j<=k; j++)
- {
- f[i][j]=max(f[i-1][j], g[i-1][j]-prices[i]);
- g[i][j]=g[i-1][j];
- if(j>0) g[i][j]=max(g[i][j], f[i-1][j-1]+prices[i]);
- res=max(res, g[i][j]);
- }
- }
- cout << res << endl;
- return 0;
- }
-
- //值得学习的代码
- #include <iostream>
- using namespace std;
-
- const int N = 1010, M = 110;
-
- int n, k, p[N];
- int f[N][M], g[N][M];
-
- int main()
- {
- cin >> n >> k;
- for(int i = 0; i < n; i++) cin >> p[i];
-
- k = min(k, n / 2);
- for(int j = 0; j <= k; j++) f[0][j] = g[0][j] = -0x3f3f3f3f;
- f[0][0] = -p[0], g[0][0] = 0;
-
- for(int i = 1; i < n; i++)
- {
- for(int j = 0; j <= k; j++)
- {
- f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i]);
- g[i][j] = g[i - 1][j];
- if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + p[i]);
- }
- }
-
- int ret = 0;
- for(int j = 0; j <= k; j++) ret = max(ret, g[n - 1][j]);
-
- cout << ret << endl;
-
- return 0;
- }
买卖股票这种类似有系列的题目,需要把核心知识点彻底弄熟。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。