赞
踩
关键在于定义状态,一般来说最起码有两个状态:当天结束的时候持有股票和不持有股票,根据限制条件再细分状态种类,明确状态之间的转移关系。
一般来说状态转移只用到上个时间的状态,可以做空间优化。
对于限制比较少的题目考虑是否可以用贪心实现。
求只交易一次的最大利润。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int f[n][2];//第一维表示天数,第二维为0表示当天结束持有股票,1表示当天结束不持有股票,数组元素表示每天不同状态下的最大利润
f[0][0] = -prices[0];
f[0][1] = 0;
for (int i = 1; i < n; i++) {
f[i][0] = max(f[i - 1][0], -prices[i]);//当天持有股票可能是昨天就持有股票,或者昨天不持有股票、今天新买入
f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i]);//当天不持有股票可能是昨天就不持有股票,或者昨天持有股票、今天新卖出
}
return f[n - 1][1];
}
};
删掉第一维
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int f[2];//第一维表示天数,第二维为0表示当天结束持有股票,1表示当天结束不持有股票,数组元素表示每天不同状态下的最大利润
f[0] = -prices[0];
f[1] = 0;
for (int i = 1; i < n; i++) {
f[0] = max(f[0], -prices[i]);
f[1] = max(f[1], f[0] + prices[i]);
}
return f[1];
}
};
由于只交易一次,找到最大的一对price差值即为答案。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minp = prices[0];
int res = 0;
for (int i = 1; i < prices.size(); i++) {
res = max(res, prices[i] - minp);
minp = min(minp, prices[i]);
}
return res;
}
};
不限制交易次数的最大利润,但不能同时进行多笔交易。
和121唯一不同的地方在于,121只能交易一次,因此如果持有股票并且在今天新买入,利润只能是-prices[i],而这题可以交易多次,因此需要加上前面的累计利润。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int f[n][2];
f[0][0] = -prices[0]; //0表示持有股票
f[0][1] = 0;//1表示不持有股票
for (int i = 1; i < n; i++) {
f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i]);//和121唯一不同的地方
f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i]);
}
return max(f[n - 1][0], f[n - 1][1]);
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int f0 = -prices[0]; //0表示持有股票
int f1 = 0;//1表示不持有股票
for (int i = 1; i < n; i++) {
f0 = max(f0, f1 - prices[i]);
f1 = max(f1, f0 + prices[i]);
}
return f1;
}
};
由于交易次数没有限制,可以当天卖出再买入,a[j] - a[i] = (a[i+1]-a[i])+(a[i+2]-a[i+1])+…+(a[j]-a[j-1]),因此只要a[i]>a[i-1]就可以将其差值累加。若连续一段a[i]>a[i-1],则相当于头尾交易一次。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
for (int i = 1; i < prices.size(); i++) {
res += max(0, prices[i] - prices[i - 1]);
}
return res;
}
};
最多可以完成两笔交易的最大利润。
添加交易次数这一维度的状态。
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); int f[n][2][3];//第一维表示天数,第二维表示是否持有股票,第三维表示今天结束时交易刺入(从买入开始计算) for (int i = 0; i < n; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 3; k++) { f[i][j][k] = 0; } } } //0表示持有股票,1表示不持有股票 //f[i][0][0]没有意义,f[i][1][0]始终等于0,因此这两项不用更新 f[0][0][0] = -1e5, f[0][0][2] = -1e5, f[0][0][1] = -prices[0]; f[0][1][0] = 0, f[0][1][1] = -1e5, f[0][1][2] = -1e5; for (int i = 1; i < n; i++) { f[i][0][1] = max(f[i - 1][0][1], f[i - 1][1][0] - prices[i]); f[i][0][2] = max(f[i - 1][0][2], f[i - 1][1][1] - prices[i]); f[i][1][1] = max(f[i - 1][1][1], f[i - 1][0][1] + prices[i]); f[i][1][2] = max(f[i - 1][1][2], f[i - 1][0][2] + prices[i]); } return max(f[n - 1][1][0], max(f[n - 1][1][1], f[n - 1][1][2])); } };
去掉天数这一维度。
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); int f[2][3]; for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { f[i][j] = 0; } } //0表示持有股票,1表示不持有股票 f[0][0] = -1e5, f[0][2] = -1e5, f[0][1] = -prices[0]; f[1][0] = 0, f[1][1] = -1e5, f[1][2] = -1e5; for (int i = 1; i < n; i++) { f[0][1] = max(f[0][1], f[1][0] - prices[i]); f[0][2] = max(f[0][2], f[1][1] - prices[i]); f[1][1] = max(f[1][1], f[0][1] + prices[i]); f[1][2] = max(f[1][2], f[0][2] + prices[i]); } return max(f[1][0], max(f[1][1], f[1][2])); } };
最多可以完成K笔交易的最大利润。
在123的基础上改变需要循环的交易次数即可,只展示优化版。
class Solution { public: int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if (n < 2 || !k) return 0; int f[2][k + 1]; for (int i = 0; i < 2; i++) { for (int j = 0; j <= k; j++) { f[i][j] = -1e5; } } f[0][1] = -prices[0]; f[1][0] = 0; for (int i = 1; i < n; i++) { for (int j = 1; j <= k; j++) { f[0][j] = max(f[0][j], f[1][j - 1] - prices[i]); f[1][j] = max(f[1][j], f[0][j] + prices[i]); } } int res = 0; for (int i = 0; i <= k; i++) { res = max(res, f[1][i]); } return res; } };
卖完一次股票后有一天的冷冻期,总交易次数没有限制。
将不持有股票细分成在冷冻期和不在冷冻期两种状态。
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); int dp[n][3]; dp[0][0] = -prices[0];//持有股票 dp[0][1] = 0;//不持有股票,不在冷冻期 dp[0][2] = 0;//不持有股票,在冷冻期 for (int i = 1; i < n; i++) { dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][0]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]); dp[i][2] = dp[i - 1][0] + prices[i]; } return max(dp[n - 1][1], dp[n - 1][2]); } };
去掉天数这一维度。
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); int dp[3]; dp[0] = -prices[0];//持有股票 dp[1] = 0;//不持有股票,不在冷冻期 dp[2] = 0;//不持有股票,在冷冻期 for (int i = 1; i < n; i++) { dp[0] = max(dp[1] - prices[i], dp[0]); dp[1] = max(dp[1], dp[2]); dp[2] = dp[0] + prices[i]; } return max(dp[1], dp[2]); } };
可以无限次地完成交易,但是你每笔交易都需要付手续费。
在122的基础上,卖出的时候减去手续费即可。
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
int f0 = -prices[0]; //0表示持有股票
int f1 = 0;//1表示不持有股票
for (int i = 1; i < n; i++) {
f0 = max(f0, f1 - prices[i]);
f1 = max(f1, f0 + prices[i] - fee);
}
return f1;
}
};
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。