文章目录
买卖股票的最佳时机
题目：买卖股票的最佳时机
思路
-
状态表示：
dp[i]表示第i天结束后，处于某个状态的最大利润，我们可以细分为，处于“买入”、“可交易”、“”三种状态dp[i][0]表示：第 i 天结束后，处于“买入”状态的最大利润dp[i][1]表示：第 i 天结束后，处于“可交易”状态的最大利润dp[i][2]表示：第 i 天结束后，处于“冷冻期”状态的最大利润
-
状态转移方程：
dp[i][0]：有两种状态可以到达i - 1天也处于“买入”状态，今天什么也不做，仍处于“买入”状态，此时最大受益和i - 1天相同，即dp[i - 1][0]i - 1天也处于“可交易”状态，今天买了股票，此时最大受益为dp[i - 1][1] - price[i]- 综上，
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
dp[i][1]：有两种状态可以到达i - 1天也处于“可交易”状态，今天什么也不做，仍处于“可交易”状态，此时最大受益和i - 1天相同，即dp[i - 1][1]i - 1天也处于“冷冻期”状态，今天什么也不做，仍处于“冷冻期”状态，此时最大受益和i - 1天相同，即dp[i - 1][2]- 综上，
dp[i][1] = max(dp[i-1][1], dp[i-1][2])
dp[i][2]：只有一种状态可以到达i - 1天也处于“买入”状态，今天卖股票，此时最大受益为dp[i][2] = dp[i - 1][0] + prices[i]
-
初始化：
- 第
0天处于买入状态，dp[0][0] = -prices[0] - `第
0天处于可交易状态，无操作，dp[0][1] =0 - 第
0天处于冷冻期状态，无操作，dp[0][2] = 0
- 第
-
填表顺序：三个表从左向右一起填写
-
返回值：卖出状态下的最大值
max(dp[n-1][1], dp[n-1][2])
C++代码
class Solution
{
public:
int maxProfit(vector<int>& prices)
{
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(3));
dp[0][0] = -prices[0];
for (int i = 1; i < n; ++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][2]);
dp[i][2] = dp[i - 1][0] + prices[i];
}
return max(dp[n - 1][1], dp[n - 1][2]);
}
};
买卖股票的最佳时机含手续费
思路
-
状态表示：第
i天结束后，所能获得的最大利润，这一天有两种状态，“买入”、“卖出”f[i]表示第i天结束后，处于“买入”状态的最大利润g[i]表示第i天结束后，处于“卖出”状态的最大利润。
-
状态转移方程：
f[i]有两种状态到达- 前一天
i - 1有股票，第i天啥也不做，收益最大为f[i - 1] - 前一天
i - 1没有股票，第i天买入股票，收益最大为g[i-1] - prices[i] - 综上，
f[i] = max(f[i-1], g[i-1] - prices[i])
- 前一天
g[i]有两种状态到达- 前一天
i - 1没有股票，第i天啥也不做，收益最大为g[i -1] - 前一天
i - 1有股票，第i天卖出股票，收益最大为f[i - 1] + prices[i] - fee - 综上，
g[i] = max(g[i-1], f[i-1] + prices[i] - fee)
- 前一天
-
初始化：
f[0]处于买入状态，此时f[0] = -price[0]g[0]处于没有股票状态，此时g[0] = 0
-
填表顺序：两个表从左向右一起填写
-
返回值：返回“卖出”状态下最后一天的最大值收益
g[n - 1]
C++代码
class Solution
{
public:
int maxProfit(vector<int>& prices, int fee)
{
int n = prices.size();
vector<int> f(n);
vector<int> g(n);
f[0] = -prices[0];
for(int i = 1; i < n; i++)
{
f[i] = max(f[i-1], g[i-1] - prices[i]);
g[i] = max(g[i-1], f[i-1] + prices[i] - fee);
}
return g[n - 1];
}
};
买卖股票的最佳时机 III
思路
-
状态表示：以某个位置为结尾，使用两个数组表示
买入和可交易两个状态，并加上一维表示交易次数f[i][j]表示第i天结束后，完成了j次交易，处于买入状态的最大利润g[i][j]表示第i天结束后，完成了j次交易，处于卖出状态的最大利润
-
状态转移方程：
-
f[i][j]有两种状态到达i - 1天处于买入，第i天什么也不做，此时最大利润f[i - 1][j]i - 1天处于卖出，第i天买股票，此时最大利润g[i - 1][j] - price[i]- 综上，
f[i][j] = max(f[i - 1][j], g[i - 1][j] - price[i])
-
g[i][j]有两种状态到达i - 1天处于买入，第i天卖出股票，，此时最大利润f[i - 1][j - 1] + price[i]i - 1天处于卖出，第i天什么也不做，此时最大利润g[i - 1][j]- 综上，
f[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + price[i])
-
-
初始化第一行，考虑第
0天只能处于买入过一次状态的情况，f[0][0] = -prices[0]，其余状态为-INF（防止减法发生越界） -
填表顺序：从上往下，从左往右
-
返回值：
卖出状态的最大值，即g表的最后一行的最大值max(g[n - 1][0], max(g[n - 1][1], g[n - 1][2]))
C++代码
class Solution
{
const int INF = 0x3f3f3f3f;
public:
int maxProfit(vector<int>& prices)
{
int n = prices.size();
vector<vector<int>> f(n, vector<int>(3, -INF));
vector<vector<int>> g(n, vector<int>(3, -INF));
f[0][0] = -prices[0], g[0][0] = 0;
for (int i = 1; i < n; i++)
for (int j = 0; j < 3; ++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]);
}
return max(g[n - 1][0], max(g[n - 1][1], g[n - 1][2]));
}
};
买卖股票的最佳时机 IV
题目：买卖股票的最佳时机 IV
思路
-
状态表示：以某个位置为结尾，使用两个数组表示
买入和可交易两个状态，并加上一维表示交易次数f[i][j]表示第i天结束后，完成了j次交易，处于买入状态的最大利润g[i][j]表示第i天结束后，完成了j次交易，处于卖出状态的最大利润
-
状态转移方程：
-
f[i][j]有两种状态到达i - 1天处于买入，第i天什么也不做，此时最大利润f[i - 1][j]i - 1天处于卖出，第i天买股票，此时最大利润g[i - 1][j] - price[i]- 综上，
f[i][j] = max(f[i - 1][j], g[i - 1][j] - price[i])
-
g[i][j]有两种状态到达i - 1天处于买入，第i天卖出股票，，此时最大利润f[i - 1][j - 1] + price[i]i - 1天处于卖出，第i天什么也不做，此时最大利润g[i - 1][j]- 综上，
f[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + price[i])
-
-
初始化第一行，考虑第
0天只能处于买入过一次状态的情况，f[0][0] = -prices[0]，，g[0][0] = 0其余状态为-INF（防止减法发生越界） -
填表顺序：从上往下，从左往右
-
返回值：
卖出状态的最大值，即g表的g[n - 1][i]
k值可能太长，我们对k进行优化
k = min(k, n / 2);
C++代码
class Solution
{
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 > 0)
g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
}
int ret = 0;
for (int i = 0; i <= k; ++i)
ret = max(ret, g[n - 1][i]);
return ret;
}
};