状态机DP：买卖股票的最佳时机

买卖股票的最佳时机

解题思路

低价买入，高价卖出。
从左到右枚举卖出价格 \(prices[i]\)。要想获得最大利润，哪天买入最好？在股票价格最低的那天买入。
注意，买入日期必须在卖出日期之前，所以我们求的是从 \(prices[0]\) 到 \(prices[i-1]\) 的最小值，可以用一个变量 \(minPrice\) 维护。
由于只能买卖一次，所以在遍历中，计算 \(prices[i]-minPrice\) 的最大值就是答案。
注：下面代码中，我们先更新 ans，再更新 minPrice，以保证 minPrice 在 prices[i] 之前。请读者思考：更新顺序能否交换？如果一定要交易一次，即使亏钱也要交易，更新顺序能否交换？

更新顺序可以交换
如果一定要交易一次，即使亏钱，不能交换。否则会出现当天买入当天卖出的无效交易，此时利润为0。但是有可能股票的价格一直下跌，不管怎么买，都是亏本生意。如 \([5,4,3,2,1]\)
作者：灵茶山艾府
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solutions/2464650/mei-ju-mai-chu-jie-ge-wei-hu-mai-ru-de-z-02ud/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码实现

点击查看代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        int price = prices[0]; // 买入价格的初始值
        int n = prices.size();
        for (int i = 0; i < n; ++i) {
            ans = max(ans, prices[i] - price);
            price = min(price, prices[i]);
        }
        return ans;
    }
};

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

买卖股票的最佳时机 II

解题思路

\(dfs(i, hold)\) 表示在第 \(i\) 天结束时，是否持有股票。

代码实现

记忆化搜索

点击查看代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // 记忆化搜索
        vector<array<int, 2>> dp(n,{-1, -1});
        auto dfs = [&](this auto&& dfs, int i, bool hold) -> int {
            if (i < 0) {
                return hold ? -INT_MAX: 0;
            }
            auto& res = dp[i][hold];
            if (res != -1) {
                return res;
            }
            if (hold) {
                res = max(dfs(i - 1, true), dfs(i - 1, false) - prices[i]);
            } else {
                res = max(dfs(i - 1, false), dfs(i - 1, true) + prices[i]);
            }
            return res;
        };
        return dfs(n - 1, false);
    }
};

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

递推
已知

\[ dfs(i, hold) = \begin{cases}max(dfs(i-1, true), dfs(i-1,false)-prices[i]), hold = true, \\ max(dfs(i-1,false), dfs(i-1,true)+prices[i]), hold = false,\end{cases}\]

因此

\[ f[i][hold]= \begin{cases}max(f[i-1][true], f[i-1][false]-prices[i]), hold = true, \\ max(f[i-1][false], f[i-1][true]+prices[i]), hold = false,\end{cases}\]

进一步得到

\[ f[i+1][hold]= \begin{cases}max(f[i][true], f[i][false]-prices[i]), hold = true, \\ max(f[i][false], f[i][true]+prices[i]), hold = false,\end{cases}\]

点击查看代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // 递推
        vector<array<int, 2>> f(n + 1,{0, 0});
        f[0][1] = -INT_MAX;
        for (int i = 0; i < n; ++i) {
            f[i + 1][1] = max(f[i][1], f[i][0]-prices[i]);
            f[i + 1][0] = max(f[i][0], f[i][1] + prices[i]);
        }
        return f[n][0];
    }
};

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

进一步优化空间复杂度

点击查看代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        //
        int f0 = 0, f1 = -INT_MAX;
        for (int i = 0; i < n; ++i) {
            int temp_f1 = f1;
            f1 = max(f1, f0-prices[i]);
            f0 = max(f0, temp_f1 + prices[i]);
        }
        return f0;
    }
};

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

最佳买卖股票时机含冷冻期

解题思路

\(dfs(i, hold)\)表示在第 \(i\) 天是否持有股票。
\(dfs(i, hold)=\begin{cases}max(dfs(i-1, false), dfs(i-1, true) + prices[i]), hold = false, \\ max(dfs(i-1, true), dfs(i-1, false) - prices[i])\end{cases}\)
第 \(i-1\) 天结束时没有股票，第 \(i\) 天买入股票 \(\rightarrow\) 第 \(i-1\) 天是冷冻期，不能卖出股票 \(\rightarrow\) 第 \(i-2\) 天一定没有股票

代码实现

点击查看代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // 记忆化搜索
        vector<array<int, 2>> dp(n, {-1, -1});
        auto dfs = [&](this auto&& dfs, int i, bool hold) -> int {
            if (i < 0) {
                return hold? -INT_MAX: 0;
            }
            auto& res = dp[i][hold];
            if (hold) {
                res = max(dfs(i-1, true), dfs(i-2, false) - prices[i]);
            } else {
                res = max(dfs(i-1, false), dfs(i-1, true) + prices[i]);
            }
            return res;
        };
        return dfs(n - 1, false);
    }
};

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

买卖股票的最佳时机(至多交易 \(k\) 次) IV

解题思路

既然有次数限制，因此我们在递归时还要记录次数
\(dfs(i,j,hold)\)表示在第 \(i\) 天结束时完成至多 \(j\) 笔交易，是否持有股票的最大利润

\[dfs(i,j,hold)=\begin{cases}max(dfs(i - 1, j, false), dfs(i - 1, j - 1, true) + prices[i]), hold = false, \\ max(dfs(i - 1, j, true), dfs(i - 1, j, false) - prices[i]), hold = true,\end{cases}\]

这道题还要注意递归边界
\(dfs(\cdot, j, \cdot)=-\infty\)，任何情况下，\(j\) 都不能为负数；
\(dfs(-1, j, 0)=0\) 这是一个合法状态；
\(dfs(-1, j, 1)=-\infty\)，非法.

代码实现

记忆化搜索

点击查看代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<array<int, 2>>> dp(n, vector<array<int, 2>>(k + 1, {-1, -1}));
        auto dfs = [&](this auto&& dfs, int i, int j, bool hold) -> int {
            if (j < 0) {
                return -INT_MAX;
            }
            if (i < 0) {
                return hold ? -INT_MAX: 0;
            }
            auto& res = dp[i][j][hold];
            if (hold) {
                res = max(dfs(i-1, j, true), dfs(i-1, j, false) - prices[i]);
            } else {
                res = max(dfs(i-1, j, false), dfs(i-1,j-1,true)+prices[i]);
            }
            return res;
        };
        return dfs(n - 1, k, false);
    }
};

时间复杂度：\(O(nk)\)
空间复杂度：\(O(nk)\)

翻译成递推
已知
\(dfs(i,j,hold)\) 表示在第 \(i\) 天结束时完成至多 \(j\) 笔交易，是否持有股票的最大利润

\[dfs(i,j,hold)=\begin{cases}max(dfs(i - 1, j, false), dfs(i - 1, j - 1, true) + prices[i]), hold = false, \\ max(dfs(i - 1, j, true), dfs(i - 1, j, false) - prices[i]), hold = true,\end{cases}\]

这道题还要注意递归边界
\(dfs(\cdot, j, \cdot)=-\infty\)，任何情况下，\(j\) 都不能为负数；
\(dfs(-1, j, 0)=0\) 这是一个合法状态；
\(dfs(-1, j, 1)=-\infty\)，非法.
翻译成递推：

\[f[i][j][hold]=\begin{cases}max(f[i-1][j][false], f[i-1][j-1][true]+prices[i]), hold=false, \\ max(f[i-1][j][true], f[i-1][j][false]-prices[i]),hold=true,\end{cases}\]

进一步，得到

\[f[i+1][j+1][hold]=\begin{cases}max(f[i][j+1][false], f[i][j][true]+prices[i]), hold=false, \\ max(f[i][j+1][true], f[i][j+1][false]-prices[i]),hold=true,\end{cases}\]

以及初始条件
\(f[\cdot][0][\cdot]=-\infty\)，
\(f[0][j][0]=0\)
\(f[0][j][1]=-\infty\)

点击查看代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<array<int, 2>>> f(n + 1, vector<array<int, 2>>(k + 2, {-INT_MAX, -INT_MAX}));
        // 初始化
        for (int j = 1; j < k + 2; ++j) {
            f[0][j][0] = 0;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < k + 1; ++j) {
                f[i+1][j+1][0] = max(f[i][j+1][0], f[i][j][1]+prices[i]);
                f[i+1][j+1][1] = max(f[i][j+1][1], f[i][j+1][0]-prices[i]);
            }
        }
        return f[n][k+1][0];    
    }
};

时间复杂度：\(O(nk)\)
空间复杂度：\(O(nk)\)

如何空间优化？

\(f[i+1]\) 只用到 \(f[i]\) 的状态，因此可以直接去掉这个维度的状态
\(f[i+1][j]\) 需要从 \(f[i][j-1]\) 转移过来，所以这里内层循环需要倒序遍历

点击查看代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<array<int, 2>> f(k + 2, {-INT_MAX, -INT_MAX});
        // 初始化
        for (int j = 1; j < k + 2; ++j) {
            f[j][0] = 0;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = k; j >= 0; --j) {
                f[j+1][1] = max(f[j+1][1], f[j+1][0]-prices[i]);
                f[j+1][0] = max(f[j+1][0], f[j][1]+prices[i]);   
            }
        }
        return f[k+1][0];    
    }
};

时间复杂度：\(O(nk)\)
空间复杂度：\(O(k)\)

改成 交易恰好/至少 \(k\) 次，要如何做？

区别主要在于边界条件。
对于恰好 \(k\) 次，我们在第 \(1\) 天开始时，由于没有任何交易，相当于恰好完成 \(0\) 次；
对于至少 \(k\) 次，至少 \(0\) 次等价于无限次交易

posted @ 2026-02-07 09:43 王仲康阅读(11) 评论(0) 收藏举报

刷新页面返回顶部

Loading

悟已往之不谏，知来者之可追。

状态机DP：买卖股票的最佳时机

买卖股票的最佳时机

解题思路

代码实现

买卖股票的最佳时机 II

解题思路

代码实现

最佳买卖股票时机含冷冻期

解题思路

代码实现

买卖股票的最佳时机(至多交易 \(k\) 次) IV

解题思路

代码实现

公告