股票买卖问题

https://discuss.leetcode.com/topic/107998/most-consistent-ways-of-dealing-with-the-series-of-stock-problems

一般化，设dp[i][j][s]表示第i天、至多交易了j次、手上有s=0或1股股票时的最大利润。

第i天这一维当然要有，手上的股票数s这一维不能少，若没有交易数限制可省掉j这一维。
有交易数限制时，可以买时算新交易改变j、也可卖时算新交易改变j，不妨买时算新交易。
有交易费用时，可以买时算费用、也可卖时算费用，不妨买时算费用、跟买股票一起花钱。
有交易冷却天数限制时，没法像通常dp[i][][]=dp[i-1][][]...那样省掉i这一维

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

非dp解：只买卖一次，若在第i天卖，应在[0,i)天最便宜时买

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

非dp解：可以无限次购买，相隔两数有利可图就购买

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

dp解同ii题，买时加上费用

int maxProfit(vector<int>& prices, int fee) {
    // 设dp[i][s]表示第i天、手上有s=0或1股股票时的最大利润
    // 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][0]-prices[i]-fee /*买股票*/)
    // 初始dp[-1][0]=0，dp[-1][1]=INT_MIN
    // dp[i][]只依赖dp[i-1][]，去掉i这维
    vector<int> dp = { 0, INT_MIN };
    for (int price : prices) {
        int dp0 = dp[0];
        dp[0] = max(dp0, dp[1] + price);
        dp[1] = max(dp[1], dp0 - price - fee);
    }
    return dp[0];
}

int maxProfit(int k, vector<int>& prices) {
    const int N = prices.size();
    if (k == 0 || N < 2) return 0;
    // k足够大时，相当于对交易次数无限制
    if (k >= N/2) return maxProfitInfK(prices);
    
    // 设dp[i][j][s]表示第i天、至多交易了j次、手上有s=0或1股股票时的最大利润
    // dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i] /*卖股票*/)
    // dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i] /*买股票，新交易*/)
    // 初始dp[-1][j][0]=0，dp[-1][j][1]=INT_MIN
    // dp在i这维上只依赖于i-1项，去掉i这维
    // 降维后，要让dp[j-1][]表示旧状态d，j要从右往左遍历
    vector<vector<int>> dp(k + 1, vector<int>({ 0, INT_MIN }));
    for (int price : prices) {
        for (int j = k; j >= 1; j--) {
            dp[j][0] = max(dp[j][0], dp[j][1] + price);
            dp[j][1] = max(dp[j][1], dp[j-1][0] - price);
        }
    }
    return dp[k][0];
}

int maxProfitInfK(vector<int>& prices) {
    // 可以无限次购买，相隔两数有利可图就购买
    const int N = prices.size();
    int ans = 0;
    for (auto i = 0; i < N - 1; i++) {
        if (prices[i] < prices[i+1]) {
            ans += prices[i+1] - prices[i];
        }
    }
    return ans;
}

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

int maxProfit(vector<int>& prices) {
    // 设dp[i][s]表示第i天、手上有s=0或1股股票时的最大利润
    // dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i] /*卖股票*/)
    // dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i] /*买股票, cooldown=1天*/)
    // 初始dp[-1][0]=0，dp[-1][1]=INT_MIN；dp[-2][0]=0，dp[-2][1]=INT_MIN
    // 递推式在i这维上只依赖i-1项、i-2项
    vector<int> prev2 = { 0, INT_MIN };
    vector<int> prev1 = { 0, INT_MIN };
    for (int price : prices) {
        vector<int> curr(2);
        curr[0] = max(prev1[0], prev1[1] + price);
        curr[1] = max(prev1[1], prev2[0] - price);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1[0];
}

algo-aha

股票买卖问题