买卖股票问题 个人思路

[Draymonders]

最简单的股票问题

只能允许一次买卖

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int mx = 0;
        int mn = INT_MAX;

        int n = prices.size();
        for (int i=0; i<n; i++) {
            mx = max(mx, prices[i] - mn);
            mn = min(mn, prices[i]);
        }
        return mx;
    }
};

[Draymonders]

可多次买卖股票

这题没做过，还是很难想出来 状态定义 & 状态转移的

那就用笨方法开始搞, 先暴力搞, 虽然会TimeOut，但是可以很好的帮我们切入这个题(TimeOut说明思路没问题，但是就是时间复杂度高)

class Solution {
public:
    // 这里的dfs返回值为 [st...ed] 最大收益 
    // check == true, 表示当前手里有股票， check==false, 当前手里没股票
    int dfs(vector<int>& prices, int st, int ed, int check) {
        if (st == ed) {
            return 0;
        }
        if (check == 0) {
            int mx1 = dfs(prices, st+1, ed, 0);
            int mx2 = dfs(prices, st+1, ed, 1) - prices[st];
            return max(mx1, mx2);
        } else {
            int mx1 = dfs(prices, st+1, ed, 1);
            int mx2 = dfs(prices, st+1, ed, 0) + prices[st];
            return max(mx1, mx2);
        }
    }
    int maxProfit(vector<int>& prices) {
        if (prices.size() < 2) return 0;
        int n = prices.size();
        int res = dfs(prices, 0, n, 0);
        return res;
    }
};

好了，既然写好了递归，那么我们就可以转动态规划了

class Solution {
public:

    int maxProfit(vector<int>& prices) {
        // dp[i][0] 当前手头有股票
        // dp[i][1] 当前手头没有股票
        int n = prices.size();
        int INF = -0x3f3f3f3f;
        vector<vector<int>> dp(n+5, vector<int>(2));
        dp[0][0] = INF;
        dp[0][1] = 0;
        for (int i=1; i<=n; i++) {
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i-1]);
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i-1]);
        }
        return dp[n][1];
    }
};

[Draymonders]

最多只能买两次的股票

同理，我们来一发 暴力求解

class Solution {
public:
    int dfs(vector<int>& prices, int st, int ed, int check, int orderNum) {
        if (st == ed) 
            return 0;
        if (orderNum >= 2)
            return 0;
        // 可以购买
        if (check == 0) {
            // 啥都不干
            int mx1 = dfs(prices, st+1, ed, 0, orderNum);
            // 买一波
            int mx2 = dfs(prices, st+1, ed, 1, orderNum) - prices[st];
            return max(mx1, mx2);
        } else { // 可以售出
            // 啥都不干
            int mx1 = dfs(prices, st+1, ed, 1, orderNum);
            int mx2 = dfs(prices, st+1, ed, 0, orderNum+1) + prices[st];
            return max(mx1, mx2);
        }
    }

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;

        return dfs(prices, 0, n, 0, 0);
    }
};

然后我们改成 动态规划

const int N = 1e5+10;
int dp[N][4][4];

class Solution {
public:
    int dfs(vector<int>& prices, int st, int ed, int check, int orderNum) {
        if (st == ed) 
            return 0;
        if (orderNum >= 2)
            return 0;
        // 可以购买
        if (check == 0) {
            // 啥都不干
            int mx1 = dfs(prices, st+1, ed, 0, orderNum);
            // 买一波
            int mx2 = dfs(prices, st+1, ed, 1, orderNum) - prices[st];
            return max(mx1, mx2);
        } else { // 可以售出
            // 啥都不干
            int mx1 = dfs(prices, st+1, ed, 1, orderNum);
            int mx2 = dfs(prices, st+1, ed, 0, orderNum+1) + prices[st];
            return max(mx1, mx2);
        }
    }

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;
        memset(dp, 0, sizeof(dp));
        int INF = -0x3f3f3f3f;

        // dp[i][j][k]  到i这个位置，j为buy/sell,已经弄了k个
        // j==0, 手里没有股票
        // j==1, 手里有股票
        dp[0][1][0] = INF; dp[0][0][1] = INF; dp[0][1][2] = INF; 
        dp[0][1][1] = INF; dp[0][1][2] = INF;

        for (int i=1; i<=n; i++) {
            for (int k=0; k<=2; k++) {
                // 手里没有股票才会涨
                if (k == 0) {
                    dp[i][0][k] = dp[i-1][0][k];
                } else {
                    dp[i][0][k] = max(dp[i-1][0][k], dp[i-1][1][k-1] + prices[i-1]);
                }
                dp[i][1][k] = max(dp[i-1][1][k], dp[i-1][0][k] - prices[i-1]);
            }
        }
        return max(max(0, dp[n][0][1]), dp[n][0][2]);
    }
};

[Draymonders]

含冷冻期的股票

卖完股票后有冷冻期, 记忆化递归

const int N = 1e5 + 100;
class Solution {
public:
    int dp[N][3];
    // check == 0  手里没股票
    // check == 1  手里有股票
    // check == 2  手里没股票，但无法交易
    int dfs(vector<int>& prices, int st, int ed, int check) {
        if (st == ed) 
            return 0;
        if (dp[st][check] != -1) {
            return dp[st][check];
        }
        if (check == 0) {
            int mx1 = dfs(prices, st+1, ed, 0);
            int mx2 = dfs(prices, st+1, ed, 1) - prices[st];
            return dp[st][check] = max(mx1, mx2);
            // return max(mx1, mx2);
        } else if (check == 1) {
            int mx1 = dfs(prices, st+1, ed, 1);
            int mx2 = dfs(prices, st+1, ed, 2) + prices[st];
            return dp[st][check] = max(mx1, mx2);
            // return max(mx1, mx2);
        } else {
            int mx1 = dfs(prices, st+1, ed, 0);
            return dp[st][check] = mx1;
            // return mx1;
        }
    }

    int maxProfit(vector<int>& prices) {
        memset(dp, -1, sizeof(dp));

        int n = prices.size();
        int res = dfs(prices, 0, n, 0);
        return res;
    }
};