全家桶 总共6道题

121. Best Time to Buy and Sell Stock
     Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i][k][0/1]
        //到第i天为止 最多进行k次交易的最大收益 0表示没有持有stock
        //着重注意第三维的状态变化
        //0可能在当天卖出股票 1可能在当天买入
        //买入的同时消耗了一次k
        
        //初始state的设定 初始的0时dp为0 初始的1dp为-∞表示不可能存在
        //仅能做一次买卖 此时k不作用
        int n = prices.size();
        int dp0 = 0; //当天不持有
        int dp1 = INT_MIN; //dp1表示当天持有股票
        for(int i = 0; i < n; ++i) {
            dp0 = max(dp0, dp1 + prices[i]);
            dp1 = max(dp1, -prices[i]);
        }
        return dp0;
    }
};

188. Best Time to Buy and Sell Stock IV
     Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

class Solution {
public:
    int profitUnlimited(vector<int>& prices) {
        //允许无限次的交易
        int n = prices.size();
        int dp0 = 0, dp1 = INT_MIN;
        for(int i = 0; i < n; ++i) {
            int temp = dp0;
            dp0 = max(dp0, dp1 + prices[i]);
            dp1 = max(dp1, temp - prices[i]);
        }
        return dp0;
    }

    int maxProfit(int k, vector<int>& prices) {
        if(k > prices.size() / 2) {
            return profitUnlimited(prices);
        }
        vector<vector<int>> dp(k + 1, vector<int> (2));
        dp[0][0] = 0; 
        for(int i = 0; i < k + 1; ++i) {
            //注意base case的界定问题
            //在整个系列中 我们不使用时间的维度 而减少了空间的复杂度
            //引入了k的维度 否则只需要01两个变量即可
            dp[i][1] = INT_MIN; //初始时不可能拥有股票
        }
        for(int i = 0; i < prices.size(); ++i) {
            for(int j = 1; j <= k; ++j) {
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = max(dp[j][1], dp[j - 1][0] - prices[i]);
            }
        }
        return dp[k][0];
    }
};

方法感谢@labuladong