주식 매매 6문항:

121 - 한 번만 매매 가능

class Solution {
public:
    int maxProfit(vector& prices) {
        const int n = prices.size();
        if (n == 0) return 0;
        //     0    
        vector> dp(n, vector(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -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], -prices[i]); //-prices[i]      dp[i-1][0]，        ，    0
        }

        return dp[n-1][0];
    }
};

class Solution {
public:
    int maxProfit(vector& prices) {
        const int n = prices.size();
        if(n == 0) return 0;

        int pre_0 = 0, pre_1 = -prices[0];
        int cur_0, cur_1;
        for(int i = 1; i < n; i++) {
            pre_0 = max(pre_0, pre_1 + prices[i]);
            pre_1 = max(pre_1, - prices[i]);
        }
        return pre_0;
    }
};

122-매매 무한회

class Solution {
public:
    int maxProfit(vector& prices) {
        const int n = prices.size();
        if(n == 0) return 0;

        int pre_0 = 0, pre_1 = -prices[0];
        for(int i = 1; i < n; i++) {
            pre_0 = max(pre_0, pre_1 + prices[i]);
            pre_1 = max(pre_1, pre_0 - prices[i]);
        }
        return pre_0;
    }
};

    int maxProfit(vector& prices) {
        const int n = prices.size();
        int pre_0 = 0, pre_1 = INT_MIN;
        for(int i = 0; i < n; i++) {
            pre_0 = max(pre_0, pre_1 + prices[i]);
            pre_1 = max(pre_1, pre_0 - prices[i]);
        }
        return pre_0;
    }

123-매매제한 2회

class Solution {
public:
    int maxProfit(vector& prices) {
        const int n = prices.size();
        if(n == 0) return 0;

        const int K = 2;
        int dp[n+1][K+1][2];
        //     0 ，      
        for (int i = 0; i <= K; i++) { // 0  
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0] - 1;
        }
        for (int i = 0; i <= n; i++) { //       0 
            dp[i][0][0] = 0;
            dp[i][0][1] = -prices[0] - 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int k = K; k >= 1; k--) {
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1]);
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1]);
            }
        }
        return dp[n][K][0];
    }
};

class Solution {
public:
    int maxProfit(vector& prices) {
        const int n = prices.size();
        if (n == 0) return 0;

        const int K = 2;
        int dp[K + 1][2];

        dp[0][0] = 0; dp[0][1] = -prices[0] - 1;
        //     0 -    k   
        for (int i = 1; i <= K; i++) {
            dp[i][0] = 0;
            dp[i][1] = -prices[i] - 1;
        }

        for (int i = 0; i < n; i++) {
            for (int k = K; k >= 1; k--) {
                dp[k][0] = max(dp[k][0], dp[k][1] + prices[i]);
                dp[k][1] = max(dp[k][1], dp[k-1][0] - prices[i]);
            }
        }
        return dp[K][0];
    }
};

188 - 매매 제한 k회 - k와 일수 n의 관계를 주의하고 특수 처리 - k가 너무 크면 제한이 없는 것과 같다

class Solution {
public:
    int maxProfit(int k, vector& prices) {
        const int n = prices.size();
        if(n == 0 || k == 0) return 0;
        //    ，    case    
        if(k * 2 >= n) return maxProfit(prices);

        int dp[n+1][k+1][2];
        //   ，            
        for(int i = 0; i <= k; i++) {
            dp[0][i][0] = 0;
            dp[0][i][1] = INT_MIN;
        }
        for(int i = 0; i <= n; i++) {
            dp[i][0][0] = 0;
            dp[i][0][1] = INT_MIN;
        }

        for(int i = 1; i <= n; i++) {
            for(int j = k; j >= 1; j--) {
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1]);
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1]); 
            }
        }
        return dp[n][k][0];
    }

    int maxProfit(vector& prices) {
        const int n = prices.size();
        int pre_0 = 0, pre_1 = -prices[0];
        for(int i = 1; i < n; i++) {
            pre_0 = max(pre_0, pre_1 + prices[i]);
            pre_1 = max(pre_1, pre_0 - prices[i]);
        }
        return pre_0;
    }
};

309. - 팔아서 하루 간격으로 살 수 있어요.

class Solution {
public:
    int maxProfit(vector& prices) {
        const int n = prices.size();
        if(n < 1) return 0;

        int dp_0_pre = 0, dp_0 = 0, dp_1 = INT_MIN;
        for(int i = 0; i < n; i++) {
            int tmp = dp_0; // dp_0   ，    dp_0_pre
            dp_0 = max(dp_0, dp_1 + prices[i]);
            dp_1 = max(dp_1, dp_0_pre - prices[i]);
            dp_0_pre = tmp;
        }
        return dp_0;
    }
};

714-수수료 추가

class Solution {
public:
    int maxProfit(vector& prices, int fee) {
        const int n = prices.size();
        if(n < 2) return 0;

        int dp_0 = 0, dp_1 = INT_MIN;
        for(int i = 0; i < n; i++) {
            dp_0 = max(dp_0, dp_1 + prices[i]);
            dp_1 = max(dp_1, dp_0 - prices[i] - fee);
        }
        return dp_0;
    }
};